найти N-й номер этой последовательности.Два набора бит

Question

Посмотрите на следующую последовательность:
3, 5, 6, 9, 10, 12, 17, 18, 20 ....

Все числа в серии имеют в точности2 бита установлены в их двоичном представлении.Ваша задача проста, вы должны найти N-е число этой последовательности.

1 <= T <= 105 <br>1 <= N <= 1014 </p>

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner (System.in);
        int t = sc.nextInt();
        while ( t > 0 ){
            int n = sc.nextInt();
            t--;
             int x =1;
            while ( n > 0 ){

               int y = 0;
                while ( y < x ){
                     n--;
                    if ( n == 0 ){
                        System.out.println((1<<x)|(1<<y));
                    }

                    y++;

                }

                x++;
            }
        }
    }
}

Это дает мне ошибку тайм-аута, могу ли я иметь оптимизированное решение для заданного диапазона входных данных

Answer 1

Изучение онлайн-энциклопедии целочисленных последовательностей

Это целочисленная последовательность, что означает, что мы должны проверять Онлайн-энциклопедия целочисленных последовательностей ^® .Он часто включает в себя довольно оптимальные алгоритмы или математические выражения для создания элементов в определенной целочисленной последовательности, поэтому ищите там, когда вам нужно оптимизированное решение.

После поиска 3, 5, 6, 9, 10, 12, 17, 18, 20 мы находим, чтоэто последовательность OEIS A018900, «Сумма двух различных степеней 2». , которая включает в себя несколько фрагментов кода, которые мы должны исследовать, чтобы определить, какой из них самый быстрый.

Самый быстрый алгоритм на странице OEIS

Соответствующий тип данных

64-битным знаковым 64 * битам long s не хватает места для хранения результата и может начать устанавливать неправильные биты после того, как n превысит 1 953 .Поскольку на практике n не будет превышать 1 014, результаты long будут хорошими.

32-разрядным int с сигнатурой не хватит места после n, превышающего 465 , поэтому они ненедостаточно велико.

Решение с использованием оптимизированного алгоритма

Решение с немного улучшенной эффективностью

Answer 2

Для моего объяснения я нумерую позицию бита от младшего значащего бита до 0. Таким образом, 3 имеет биты 0 и 1 установлены.5 имеет биты 0 и 2 и т. Д.

В 0-значном числе самый старший установленный бит - это бит 0 (потому что тогда нет другого бита для установки).1 число, где это бит 1 (3).Два числа, где это бит 2 (101 = 5 и 110 = 6).И так далее. m числа, где самый старший установленный бит - это бит m .

Это, в свою очередь, означает, что до и включая числа, в которых бит b более значимый из двух установленных битов - это b * ( b + 1) / 2 числа.Давайте на минутку предположим, что это равно N .Тогда согласно формуле для решения квадратного уравнения b = (sqrt (8 * N + 1) - 1) / 2. Если это не целое число, это потому, что N не совсем соответствует формуле, которую я сказал.Округлите, чтобы найти b , а затем найдите, какой другой бит должен быть установлен, чтобы все было согласовано.

Я специально не даю вам полного решения.Вы хотели решить эту проблему, вы делаете работу.Я надеюсь, что мои данные полезны.

Другая, меньшая, но более простая, оптимизация: Найдите наибольшее N среди тестовых случаев.Вычислите числа последовательности до этого наибольшего N и поместите их в массив (вы можете изменить свой код из вопроса, чтобы сделать это).Затем распечатайте все требуемые результаты, ища их в массиве.Придирки к языку: можно утверждать, что это не буквально оптимизация , поскольку это слово происходит от латинского optimus , что означает best , и оно не дает максимально быстрогопрограмма.