Soliciting Ideas

general
1

Long back in our college, we had a hiring challenge from a certain company that aksed us to solve this :
" Count the number of integers in a given range [l, r] that have prime number of set bits.
(Like 5 => 101 has 2 bits set and 2 is prime so it will counted and so on)
l, r can go up to 10^18
Time limit : 1 second
I do not remember if r-l < 1e6 or not but if not, how to approach this problem

Before I trigger any of you good people :joy: , yes I have first googled and I’ve had a look at the geeks for geeks implementation and the similar leetcode question, both of which apply normal brute force.

I have thought of this : since the no of prime number of set bits is small even in that huge range, find the resulting combinations and add

For some context , suppose n is between 0-10 we know that
0000 - 0 set bits
0001 - 1 set bit
0010 - 1 set bits
0011 - 2 set bits +1
0100 - 1 set bits
0101 - 2 set bits +1
0110 - 2 set bits +1
0111 - 3 set bits +1
1000 - 1 set bits
1001 - 2 set bits +1
1010 - 2 set bits +1

My small noob takeaways / thoughts

Now we notice two things, from 1-10 we can have only prime nos { 2 , 3 } so can something be done like enumerating the nos that have 2 ones
Here 5 numbers have 2 ones
And finding numbers that have 3 ones, here 1 number has 3 set bits and summing all the combinations together so is this approach feasible?
I coded the brute force and I am not sure if the numbers 3,5,6,7,9,10 they look like they follow a pattern , which leads me to my next question, how do I know fast if it’s a pattern oriented question
Now I know that the bits follow a pattern like lsb will be 0,1,0,1… and next left bit will be 0,0,1,1… and so on

I had all these ideas running in my head when this challenge happened, it was for 2 I think and there were 2-3 questions, I couldn’t implement any of my ideas and none of them came to fruition and I tanked pretty badly. I’m used to long here where we have days to think and come to an amazing conclusion after loads of efforts, have to work on my short contests.

Are any of these ideas in the right direction!

Now, lastly I’m sorry to subject you all to this huge essay :slight_smile: but I thought it would be better if I described what effort I’d taken and where I stand in my train of thought and not simply fishing for solutions as an easy way out.

Approach, suggestions and criticisms are very welcome :slight_smile:

@ssjgz @vijju123

1 Like
2

I feel that this will be a very classical Digit DP question if constraints on L and R are large. It will be a standard digit dp question where you need number of integers in the given range such that the sum of digit is K. The only difference is that here the base is 2 instead of 10, so we put only 0 or 1 instead of usual [0,9] in digits.

Answer for range [1,R] will be DP[R][K] for \forall K such that K is prime. Answer for range [L,R] will be answer for range [1,R]- ans for range [1,L-1]

(PS: DP[N][K] is loosely made. There are usually more states to take care of.)

2 Likes
3

Thanks :slight_smile: , I will read up on digit dp and try to solve it .

4

You do not need DP I think.
Let COUNT(N) return the count of numbers with given property in [0, N].
Let B(N) be the binary representation of N.
Now let’s define another function SOLVE(B(N), next, alreadySet).
If B(N)[next] = 0 just return SOLVE(B(N), next + 1, alreadySet).
Otherwise, if you set B(N)[next] = 0, any combination of successive bits will produce a number <= N (the prefix up to next - 1 is fixed).
For any prime P in [0, 64], if alreadySet <= P <= |B(N)| - next - 1 sum BIN(|B(N)| - next - 1, p - alreadySet) (where BIN is the binomial coefficient).
Then return the sum + SOLVE(B(N), next + 1, alreadySet + 1).
When next == |B(N)| return 1 if alreadySet is prime and 0 otherwise.
COUNT(N) simply produces B(N) and return SOLVE’s result.
To get the result for [L, R] just return COUNT( R) - COUNT(L - 1).

1 Like
5

Thanks , I do not completely understand this yet , but I got the gist of the idea :slight_smile:
I will try my hand at it

1 Like
6

Don’t worry. However, if you want this is my code.

public static final long MOD = (long)1E9 + 7;
public static int[] primes = new int[] {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61};
public static long[] fact;

public static long modInv(long n) {
	return BigInteger.valueOf(n).modInverse(BigInteger.valueOf(MOD)).longValue();
}

public static long bin(int n, int k) {
	return fact[n] * modInv(fact[n - k]) % MOD * modInv(fact[k]) % MOD;
}

public static long solve(char[] n, int next, int alreadySet) {
	if(next == n.length)
		return Arrays.binarySearch(primes, alreadySet) >= 0 ? 1 : 0;
	if(n[next] == '0')
		return solve(n, next + 1, alreadySet);
	long ans = 0;
	for(int p : primes) {
		if(p < alreadySet)
			continue;
		if(p - alreadySet > n.length - next - 1)
			break;
		ans = (ans + bin(n.length - next - 1, p - alreadySet)) % MOD;
	}
	return (ans + solve(n, next + 1, alreadySet + 1)) % MOD;
}

public static long count(long n) {
	return solve(Long.toBinaryString(n).toCharArray(), 0, 0);
}

public static void main(String[] args) throws IOException {
	fact = new long[65];
	fact[0] = 1;
	for(int i = 1; i <= 64; i ++)
		fact[i] = fact[i - 1] * i % MOD;
	long l = in.nextLong();
	long r = in.nextLong();
	System.out.println((count(r) + (l == 0 ? 0 : MOD - count(l - 1))) % MOD);
}
2 Likes
7

Thanks a lot for this , i will look at this after I’ve had a go implemeting :slight_smile:
Much appreciated

1 Like