Большое двоичное число

Question

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

Проблема: вам присвоено число n . Найдите десятичное значение числа, образованного конкатенацией двоичного представления первых n натуральных чисел. Выведите ответ 10 ^ 9 + 7.

Формат вывода: Выведите ответ по модулю 10 ^ 9 + 7

Ограничение: 1 <= n <= 10 ^ 9 </p>

Sample input: 3
Sample Output: 27
The binary representation of 1: 1
The binary representation of 2: 10
The binary representation of 3: 11
Concatenated string: 11011 -> Decimal representation is 27.

Первое сомнение, которое у меня возникло: «по модулю 10 ^ 9 + 7», я понимаю, это предел для количества символов, но я не знаю, как его интерпретировать.

Второе Часть вопроса связана с решением: Введите: 20

Binary representation of 2 : 10.
Binary representation of 3 : 11
Binary representation of 4 : 100. 
Binary representation of 5 : 101
Binary representation of 6 : 110
Binary representation of 7 : 111
Binary representation of 8 : 1000
Binary representation of 9 : 1001
Binary representation of 10 : 1010
Binary representation of 11 : 1011
Binary representation of 12 : 1100
Binary representation of 13 : 1101
Binary representation of 14 : 1110
Binary representation of 15 : 1111
Binary representation of 16 : 10000
Binary representation of 17 : 10001
Binary representation of 18 : 10010
Binary representation of 19 : 10011
The binary representation of 20: 10100
Concatenated string: 11011100101110111100010011010101111001101111011111000010001100101001110100

Как вы порекомендуете решать эту проблему?

Это мой текущий код:

public long FindBigNum(long n) {
    System.out.println("");
    System.out.println("Input: " + n);
    StringBuilder binaryRepresentation = new StringBuilder();
    for(Long i = 1l; i <= n; i++){
        System.out.println("Binary representation of " + i + " : " + Long.toBinaryString(i));
        binaryRepresentation.append(Long.toBinaryString(i));
    }
    System.out.println("Concatenated string: " + binaryRepresentation.toString());
    //System.out.println("Binary representation: " + binaryRepresentation.toString());
    long longRepresentation = parseLong(binaryRepresentation.toString(), 2);
    //System.out.println("longRepresentation: " + l);
    return longRepresentation;   
}

public long parseLong(String s, int base){
    return new BigInteger(s, base).longValue();
}   

Answer 1

Первое сомнение, которое у меня возникло: «modulo 10 ^ 9 + 7», я понимаю, это предел количества символов, но я не знаю, как его интерпретировать.

Это означает получение остатка при делении на это значение. Это значение 1000000007 (я предполагаю, что курсор - это возведение в степень).

Вот как я подхожу к этому.

• Сгенерируйте конкатенированные строки, как вы это делали.
• Используйте BigInteger для преобразования из двоичного в десятичное, а затем возьмите mod с помощью метода BigInteger mod.

Это в конечном итоге будет очень медленным и неэффективным. Однако он служит средством контроля, позволяющим вам исследовать оптимальные способы сделать это. Возможно использование StringBuilder и предварительное выделение памяти для него. Написание собственного int в процедуру двоичного преобразования, et c. Это может даже потребовать больше математического решения (например, теории чисел), чем программного решения.

Но вы можете сравнить свои результаты с решением BigInteger, чтобы проверить, работает ли оно.