Find remainder modulo k of digit formed by concatenating first n binary numbers

help
1

First construct concatenated digit using binary representations of 1 to n numbers.

  • Suppose n = 2. The we have concatenated binary digit = bin(1) || bin(2) = 1 || 10.

Convert this number to base 10 assuming LSB on right.

  • In this case, converted digit = 6 in base 10.

Let this number be k. Task is to find k modulo 10^9 + 7.

n can be as big as 10^9.

2

Can you please send the problem link?

3

Interview question, I don’t have link.

4

Solution: static long FindBigNum(long n) {
long startTime = System.currentTimeMillis();
long res = 1l;
for(long i=2;i<=n;i++) {
res =((res<<countBits(i))%MOD+i%MOD)%MOD;
}
System.out.println("EndTime: "+(System.currentTimeMillis()-startTime));
return res%MOD;
}

O(n).

Problem is that I for large input ~999999999, I am getting TLE. Need to find a solution with O(n/2) or O(logn) complexity;

Please help

5

develop a new logic such that you run the code with step value or only till 1/2 or ()**1/2 times the original range

Divide or multiply by a constant value to get O(log N) time complexity

1 Like