Алгоритм относительно прост. Вместо того, чтобы идти по одному числу за раз и накапливать число единиц, которое имеет его двоичное представление, мы будем пропускать все ближе и ближе к цели, используя ряд функций {a (m), b (m), c (m) .. .} чтобы приблизиться к цели и оставить в конце не более пары цифр для добавления вручную. Каждая функция будет иметь формат =2%5E%7Bm-1%7D*m+x*2%5E%7Bm%7D)
, где x - номер функции (для a (m) x = 0, для b (m) x = 1 ...).
Эти функции основаны на признаке двоичных чисел: во всех числах от 1 до
вы можете узнать количество единиц в его двоичных представлениях {1,2 ... n}.
Давайте посмотрим на число 
,, которое находится в двоичном 1111. Вы можете узнать количество единиц во всех числах от 1 (0001) до 15 (1111) - это подсчет, сколько способов вы можно поставить 1 в 4 местах (4) раза 1, плюс сколько раз вы можете положить 2 в 4 места (6) раз 2, плюс сколько раз вы можете положить 3 в 4 места (4) раз 3 плюс сколько способов вы можно поставить 4 в 4 местах (1) раз 4. Таким образом, общее число равно 32, что также 
. вы заметите, что для любого такого числа n = , накопленное число из 1 - это 
. Давайте назовем эту функцию a (m), как было решено выше (здесь x = 0, поэтому нет необходимости в добавлении элемента в этом). Например:
- 1 = a (1) =
= 
= 
= 1.
- 3 = a (2) =
= 
= 
= 4.
- 7 = a (3) =
= 
= 
= 12.
- 15 = a (4) =
= 
= 
= 32.
- 31 = a (5) =
= 
= 
= 80.
и так далее. поэтому для числа 15, которое является 
,, мы вычисляем a (4) и получаем 32 накопленных единицы. Мы также заметим, что число содержит ровно m 1 (все цифры установлены в 1).
Зная, что вы берете свое число k, находите ближайшее a (m), которое меньше k, тогда как a (m + 1) будет больше k. Если a (m + 1) только на m + 1 больше, чем k, возьмите a (m + 1) в качестве ответа и завершите алгоритм. Поскольку a (m + 1) имеет по крайней мере m + 2, это означает, что вы не можете накопить все k 1, которые вам нужны, без него.
Если k больше, чем m + 1, больше, чем (m + 1), но больше, чем (m), вам потребуется приближение второго шага путем определения второй функции - назовем ее b (m). Мы определим b (m) = 
. Это число будет эквивалентно 
точно (не , как это было для функции a) Например:
- 2 = b (1) =
= 
= 
= 1 + 2 = 3.
- 4 = b (2) =
= 
= 
= 4 + 4 = 8.
- 8 = b (3) =
= 
= 
= 12 + 8 = 20.
- 16 = b (4) =
= 
= 
= 32 + 16 = 48.
- 32 = b (5) =
= 
= 
= 80 + 32 = 112.
Причина, по которой мы определили b, заключается в том, чтобы описать уникальную разницу в накоплении единиц между первой серией чисел и второй следующей серией чисел - добавление другого наиболее значимого 1 для них каждого из чисел во второй партии. Вот почему мы теперь смотрим на , а не на .
Добавив две функции, мы можем получить наш номер n. Если после двух приближений нам все еще не хватает конечного k, мы можем накапливать одно за другим числа, пока не достигнем k.
Давайте предположим, что k = 50. Мы знаем, что a (4) - самое близкое, что мы можем получить, будучи наибольшим числом, которое все еще ниже 50. a (5) приведет нас к 80, как мы видели выше. Таким образом, (4) является первой половиной решения, которое составляет 15.
Остальные 1 - 50-32 = 18. Нам нужно увидеть, сколько чисел нам нужно обработать за 15, чтобы накопить как минимум еще 18 единиц. вычисляя функцию b, мы видим, что b (2) приближает нас, а b (3) на 2 больше. Так как мы знаем, что число, представленное b (3), содержит по крайней мере 4 1, мы знаем, что это число, которое нам нужно - любое число ниже него будет иметь только 16 1, и нам нужно 18. Итак, мы идем с b (3 ), который равен 
или 8. Результат равен 15 + 8 = 23, и это наименьшее число, которое имеет не менее 50 накопленных единиц во всех двоичных {1,2..23} представления.
Если нам нужно пройти еще одну итерацию, мы можем определить =2%5E%7Bm-1%7D*m+2*2%5E%7Bm%7D)
, и это сделает нас еще ближе. Например, для k = 120 мы получим (5) + b (3) = 100 и добавление c (2) добавит нас еще 12 к 112. Мы можем вручную добавить недостающие 8 чисел или решить добавить =2%5E%7Bm-1%7D*m+3*2%5E%7Bm%7D)
, что приведет нас к 119, добавив (5) + b ( 3) + с (2) + d (1). Это означает, что следующее число должно быть наименьшим n, у которого накоплено k или более единиц. a (5) = 31, b (3) = 8, c (2) = 4 и d (1) = 2, поэтому n = 46 - следующее число по сравнению с 119 1, собранными на 45.
Сложность O (log (k)) - у нас есть log (k) шагов, чтобы получить a (m) и еще не более log (k) накоплений, чтобы получить b (m) и наше возможное n.
КОД
//This represents the function a(m), b(m)... etc.
public int getFuncResult(int funcNum, int arg) {
Double result = Math.pow(2,arg-1)*arg+funcNum*Math.pow(2,arg);
return result.intValue();
}
//This is the iterative algorithm described: add a(m)+b(m)... until k
public int countOnesToKIter(int k) {
int funcNum = 0;
int counter = 0;
int retVal = 0;
int exponent = 0;
while (k > 0) {
//for the current function, find the appropriate m
while (k > counter) {
exponent++;
counter = getFuncResult(funcNum, exponent);
}
//if the last number contains more 1's than the difference, use it.
if (counter-k < exponent) {
counter=getFuncResult(funcNum, exponent-2);
retVal+=Math.pow(2,exponent-2);
} else {
counter = getFuncResult(funcNum, exponent-1);
retVal+=Math.pow(2,exponent-1);
}
funcNum ++;
exponent=0;
k = k-counter;
counter = 0;
}
return retVal;
}