Big binary number

I'm trying to solve a problem, for the basic scenario it's working, nevertheless, I know that it is not optimal and has several faults.

Problem: You are given a number n. Find the decimal value of the number formed by the concatenation of the binary representation of the first n positive integers. Print the answer 10^9 + 7.

Output format: Print the answer modulo 10^9 + 7

Constraint: 1 <= n <= 10^9

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.

The first doubt that I have is: "modulo 10^9 + 7", I understand is the limit for the number of chars, but I don't know how to interpret it.

The second part of the question is with the solution: Input: 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

How would you recommend to tackle this kind of problem?

This is my current code:

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();
}   

1 answer

  • answered 2020-08-06 17:25 WJS

    The first doubt that I have is: "modulo 10^9 + 7", I understand is the limit for the number of chars, but I don't know how to interpret it.

    That means to get the remainder when dividing by that value. It is the value 1000000007 (I am assuming the caret is exponentiation).

    Here is how I would approach this.

    • Generate your concatenated strings as you have been.
    • Use BigInteger to convert from binary to decimal and then take the mod with the BigInteger mod method.

    That will ultimately be very slow and not efficient. However, it serves as a control to allow you to investigate optimal ways of doing it. Perhaps employing StringBuilder and pre-allocating storage for it. Writing your own int to binary conversion routine, etc. It may even require more of a math solution (e.g. number theory) than a programming solution.

    But you can compare your results to the BigInteger solution to verify if it is working.