Попытка найти число x, которое удовлетворяет n + x = n ^ x, терпит неудачу с тайм-аутом

Я пытаюсь решить следующую проблему из раздела "Манипуляция бит" на сайте Hacker Rank с использованием новых возможностей Java 8, таких как Stream s.

Описание проблемы:

Учитывая целое число n, найдем каждое x такое, что:

  • 0 <= x <= n
  • n + x = n ^ x

где ^ обозначает побитовый оператор XOR. Затем напечатайте целое число, обозначающее общее число x, удовлетворяющее указанным выше критериям.

Ограничения

  • 0 <= n <= 10 15

Пример ввода: 5

Результат выборки: 2

Объяснение:

При n = 5 значения x и 0 удовлетворяют условиям:

  • 5 + 0 = 5 ^ 0 = 5
  • 5 + 2 = 5 ^ 2 = 7

Таким образом, мы печатаем 2 как наш ответ.

Пример ввода: 10

Результат выборки: 4

Объяснение:При n = 10 значения x, 0, 1, 4 и 5 удовлетворяют условиям:

  • 10 + 0 = 10 ^ 0 = 10
  • 10 + 1 = 10 ^ 1 = 11
  • 10 + 4 = 10 ^ 4 = 14
  • 10 + 5 = 10 ^ 5 = 15

Таким образом, мы печатаем 4 как наш ответ.

Мой код выглядит следующим образом:

public class SumVsXor 
{
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long count = LongStream.rangeClosed(0, n)
                               .filter(k -> k + n == (k ^ n))
                               .count();
        System.out.println(count);  
    }
}

Проблема заключается в том, что этот код не передает все тестовые примеры.

Он работает при малых значениях n, но для больших значений, таких как 1000000000000000, он не выполняется из-за таймаута.

Интересно, не может ли LongStream обрабатывать Stream с помощью этого множества элементов.

Ответы

Ответ 1

Проблема с вашим кодом заключается в том, что он очень неэффективен. Для случая n==1000000000000000 конвейер Stream выполняет операции 1,000,000,000,000,000 добавления и XOR, что занимает много времени. Тестирование для каждого номера между 0 и n, если бы n + x == n ^ x потребовалось бы много времени, даже если вы используете цикл for вместо Stream s.

Вместо того, чтобы проверять все числа от 0 до n, вы должны попытаться выяснить лучший способ рассчитать требуемое общее количество x. Тот факт, что эта проблема появляется в разделе "Манипуляция бит", должна дать вам подсказку для просмотра битов чисел, удовлетворяющих n + x == n ^ x.

Рассмотрим случай n==1000000000000000. Бинарное представление этого большого числа

0000000000000011100011010111111010100100110001101000000000000000
              ===   == = ====== = =  =  ==   == =
                 ---  - -      - - -- --  ---  - ---------------
~~~~~~~~~~~~~~

Для того, чтобы n + x был равен n ^ x, x должен иметь значение 0 во всех битах, соответствующих битам 1 n (помеченных = выше), и значение 0 или 1 в битах, соответствующих битам 0 n (помечено знаком - выше). Это не включает ведущий 0 (помеченный ~ выше), так как x должен быть <= n, поэтому любой ведущий 0 в n также должен иметь значение 0 в x.

Это означает, что общее число x, для которого n + x == n ^ x составляет
2 номер 0 в n, не включая ведущий 0 s.

В случае n = 1000000000000000 существуют 30 такие 0 биты, поэтому общее число x, удовлетворяющее требованию, равно 2 30.

Здесь один из способов вычислить общее число x:

long n = 1000000000000000L;
int zeroBitsCount = 0;
while (n > 0) {
    if (n % 2 == 0) {
        zeroBitsCount++; // counts the number of non-leading 0 bits
    }
    n = n >> 1; // divide n by 2 in order to examine the next bit in the next iteration
}
long total = 1L << zeroBitsCount; // the total is 2^(the 0 bits count)

Ответ 2

Я пришел к одному и тому же результату, но через другое объяснение, поэтому подумал, что могу опубликовать его здесь.

В ответе Эрана пришел тот же вывод, что и я: для изменения нулей в двоичном представлении начального числа - это довольно просто.

Предположим, что наше число

101010100

поэтому он имеет 5 нулей.

вам понадобятся все возможные комбинации:

  • одиночный нуль
  • два нуля
  • три нуля
  • четыре нули
  • пять нулей

который на самом деле:

 comb(1,5) + comb(2,5) + comb(3,5) + comb(4,5) + comb (5,5)

которая является известной формулой, равной:

pow (2, n)//где n равно пяти в нашем случае

отсюда решение очевидно...

Ответ 3

public static void main (String[] args) {
    Scanner in = new Scanner (System.in);
    long n = in.nextLong();
    long count = 1L << (64-Long.bitCount(n)-Long.numberOfLeadingZeros(n));
    System.out.println(count);
}

Ответ 4

Это простой вопрос, если вы немного знаете о XOR. Я не знаю много о java. Но я могу объяснить в python.

1. Сначала преобразуем число в двоичное. 2.Вставьте количество нулей в этом двоичном числе. 3.print 2 ^ (число нулей) и что оно.

Вот мой код python.

n = int(input())
sum = 0
if n!=0:
    n=str(bin(n))
    for i in range(len(n)):
            if n[i]=='0':
           sum = sum + 1
    print(2**(sum-1))
else: print(1)

Причиной уменьшения суммы на 1 является, в python, преобразование числа в двоичный формат в этом формате. например: 0b'10101.