Найти K-е наименьшее число для выражения (2 ^ x) * (3 ^ y) * (5 ^ z)

Question

в выражении

2 ^x * 3 ^y * 5 ^z

x, y и z могут принимать неотрицательные целые значения (> = 0).

Таким образом, функция будет генерировать серию чисел 1,2,3,4,5,6,8,9,10,12,15,16....

• У меня есть решение о грубой силе.
• Я бы в основном повторял цикл, начинающийся с 1, и на каждой итерации я бы обнаружил, что текущие числовые коэффициенты только из набора 2,3 или 5.

Я хотел бы иметь элегантный алгоритм.

Это вопрос интервью.

Answer 1

Это можно решить с помощью очереди приоритетов, в которой хранятся триплеты (x, y, z) , отсортированные по ключу 2 ^x 3 ^y 5 ^г .

1. Начинайте только с триплета (0, 0, 0) в очереди.

2. Удалите триплет (x, y, z) с наименьшим ключом из очереди.

3. Вставьте три тройки (x + 1, y, z) , (x, y + 1, z) и (x, y, z + 1) в очереди. Убедитесь, что вы не вставили ничего, что уже было там.

4. Повторяйте с шага 2, пока не удалите k триплетов. Последний удаленный твой ответ.

По сути, это становится сортированным обходом этого ориентированного ациклического графа. (Первые три уровня, показанные здесь, фактический график, конечно, бесконечен).

Answer 2

На этой странице перечислены решения на нескольких языках программирования.Как обычно, версия на Haskell особенно компактна и проста:

hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
     where merge (x:xs) (y:ys)
            | x < y = x : xs `merge` (y:ys)
            | x > y = y : (x:xs) `merge` ys
            | otherwise = x : xs `merge` ys

Обновление Как заметил Уилл Несс, в Data.List.Ordered есть готовая функция, которая является лучшим выбором.чем мой merge (и у него тоже лучшее имя).

import Data.List.Ordered (union)
hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming

Answer 3

Самое простое решение, которое я могу придумать:

    int[] factors = {2, 3, 5};
    int[] elements = new int[k];
    elements[0] = 1;
    int[] nextIndex = new int[factors.length];
    int[] nextFrom = new int[factors.length];
    for (int j = 0; j < factors.length; j++) {
        nextFrom[j] = factors[j];
    }
    for (int i = 1; i < k; i++) {
        int nextNumber = Integer.MAX_VALUE;
        for (int j = 0; j < factors.length; j++) {
            if (nextFrom[j] < nextNumber) {
                nextNumber = nextFrom[j];
            }
        }
        elements[i] = nextNumber;
        for (int j = 0; j < factors.length; j++) {
            if (nextFrom[j] == nextNumber) {
                nextIndex[j]++;
                nextFrom[j] = elements[nextIndex[j]] * factors[j];
            }
        }
    }
    System.out.println(Arrays.toString(elements));

Это генерирует первые k элементов этого набора в порядке возрастания в O (k) пространстве и времени.

Обратите внимание, что необходимо потреблять nextNumber из всех j, которые его предоставляют, для устранения дубликатов (2 * 3 = 3 * 2 в конце концов).

Редактировать:В алгоритме используется тот же подход, что и в haskell, опубликованном nm

Answer 4

Это может быть больше, чем ваши знания об алгоритмах, которые включают в себя то, как вы думаете, решаете проблемы и работаете в команде.

Важно иметь достойную спецификацию проблемы, прежде чем начать. Некоторые из неизвестных, как описано, включают в себя:

• есть ли границы для K?
• Вы хотите известный алгоритм или все в порядке?
• использование памяти против времени вычислений? (может быть один или другой вопрос)
• как быстро нужно вычислять, сколько времени мне нужно на его разработку?
• должны ли результаты кэшироваться?

Спрашивать интервьюера о некоторых или всех из этих вопросов может быть как минимум так же важно, как и возможность ответить на заданный вопрос. Конечно, вы можете нарисовать себя в углу таким образом, что даже может быть частью теста ...

Answer 5

Поскольку проблема может быть преобразована в нахождение K-го наименьшего числа

 f(x,y,z) = x log(2) + y log(3) + z log(5),

алгоритм может быть следующим

1. начинается с f (x, y, z) = f (0,0,0)

2. учитывая текущее наименьшее число f (i, j, k) = v, вы должны найти (x, y, z) такое, что f (x, y, z) будет ближайшим к v и> v. С

   log(2)<log(3)<2log(2)<log(5)

   Мы можем сказать

   0<=i-2<=x<=i+2, 0<=j-1<=y<=j+1 & 0<=k-1<=z<=k+1 such that f(x,y,z) > v

Так что, так как нужно найти минимум 45 значений на каждом шаге, и я бы сказал, что это алгоритм O (K). Конечно, число 45 можно уменьшить, наложив больше условий, таких как (x, y, z)! = (I, j, k).

Answer 6

Ниже приведено рабочее решение на основе Java для нахождения k-го наименьшего числа, которое имеет коэффициенты только 2,3 и 5. Здесь 2 * 3 * 5 рассматривается как наименьший коэффициент.

import java.util.Comparator;
import java.util.PriorityQueue;
public class KthSmallestFactor {

    public static void main(String[] args){

        for(int i=1;i<=10;i++){
            System.out.println(kthSmallest(i));
        }
    }

    private static int kthSmallest(int k){
        PriorityQueue<Triplet> p = new PriorityQueue<Triplet>(10, new Comparator<Triplet>() {
            public int compare(Triplet t1, Triplet t2) {
                int score1 = (int) (Math.pow(2, t1.a) * Math.pow(3, t1.b) * Math.pow(5, t1.c)) ; 
                int score2 = (int) (Math.pow(2, t2.a) * Math.pow(3, t2.b) * Math.pow(5, t2.c));
                return score1 -score2;
            }
        });

        p.add(new Triplet(1, 1, 1));
        int count =1;
        while(count <k){
            Triplet top = p.poll();
            count++;
            int a = top.a;
            int b = top.b;
            int c = top.c;
            Triplet t = new Triplet(a+1, b, c);
            if(!p.contains(t)){
                p.add(t);
            }
            t = new Triplet(a, b+1, c);
            if(!p.contains(t)){
                p.add(t);
            }
            t = new Triplet(a, b, c+1);
            if(!p.contains(t)){
                p.add(t);
            }
        }
        Triplet kth = p.poll();
        System.out.println("a: "+kth.a+"b: "+kth.b+"c: "+kth.c);
        return (int) (Math.pow(2, kth.a) * Math.pow(3, kth.b) * Math.pow(5, kth.c));
    }
}
class Triplet{
    int a ;
    int b;
    int c;

    public Triplet(int a , int b, int c){
        this.a = a;
        this.b=b;
        this.c = c;
    }

    public boolean equals(Object other){
        Triplet t = (Triplet)other;
        return this.a== t.a && this.b==t.b && this.c == t.c; 
    }
}

Answer 7

Существует очень элегантное решение этой проблемы. Алгоритм и кодирование просты. Временная сложность O (n)

Я где-то видел подобную проблему. Задача состояла в том, чтобы сгенерировать числа вида 2 ^ x.3 ^ y в порядке возрастания.

Так что вот.

int kthsmallest(int k){

    int two = 0, three = 0, five = 0;
    int A[k];
    A[0] = 1;
    for (int i=1; i<k; i++){
        int min = (A[two] * 2 <= A[three] * 3)? A[two] * 2: A[three] * 3;
        min = (min <= A[five] * 5)? min: A[five] * 5;
        A[i] = min;
        if (min == A[two] * 2)
            two++;
        if (min == A[three] * 3)
            three++;
        if (min == A[five] * 5)
            five++;
    }
    return A[k-1];
}

Алгоритм в основном - сохранить три указателя для x , y , z . В коде я использовал два , три и пять . На каждой итерации проверяйте, какая из них меньше ( 2 ^ x , 3 ^ y или 5 ^ z ). Поместите это число в индекс ith и увеличьте соответствующее значение на x или y или z . Если имеется более одного минимального значения, то увеличьте оба указателя.

Answer 8

Это числа Хэмминга , которые я использовал в качестве примера в SRFI-41 . Это был код, который я использовал там:

(define hamming
  (stream-cons 1
    (stream-unique =
      (stream-merge <
        (stream-map (lsec * 2) hamming)
        (stream-map (lsec * 3) hamming)
        (stream-map (lsec * 5) hamming)))))

Answer 9

Начните с x = y = z = 0; На каждой итерации вычисляют три n:

nx = 2^(x+1)*3^y*5^z
ny = 2^x*3^(y+1)*5^z
nz = 2^x*3^y*5^(z+1)

Найдите наименьшее n из трех:

n = min(nx, ny, nz).

Увеличьте либо x, y, либо z:

If n == nx -> x = x + 1
If n == ny -> y = y + 1
If n == nz -> z = z + 1

Остановитесь после K-й итерации и верните n.