minimum no of integers of the form 2^l required

Question

I came across this problem today, in this we have been given a sorted array a[] in ascending order and then we find sum of the numbers 2a1, 2a2, 2a3, ..., 2an and we need to find the minimum number of additional integers of the type 2l (l is non-negative) that must be required such that the sum total of all integers present equals 2k - 1 for some integer k (k is non-negative).

For example:

The input consists of an integer n in first line. The second input line contains n space-separated integers a(1), a(2), ..., a(n).

Example 1:
3
0 1 2

The answer in this case is 0 since 2⁰+2¹+2² = 7 is already in the form of 2^k-1 for k=3.

Example 2:
3
2 4 5

the answer for this case is 3 since 2²+2⁴+2⁵=52 and to make it of 2^k-1 we have 63 so required 2⁰,2¹,2³ as the three term.

I approached this problem to find the sum and then count the number of 1's in the binary representation and then answer equals max(a[i])-count.

But the problem that I get is the given constraints in the problem
1 ≤ n ≤ 10^5
0 ≤ a[i] ≤ 2*10^9

Can someone help? This problem i got in a programming contest and solutions accepted in 2.6 MB memory. So,Storing or taking array bits of 2*10^9 bits would not be better.There will be a different approach or idea i think.

Answer 1

You don't need 2*10^9 bits of memory to solve this problem. The boundary on n (n < 10^5) suggest another solution:

(1) Sort the a_i :

3 3 3 3 3 5 7 9

(2) Get rid of the duplicates by finding consecutive copies via binary search. In this case, you have 5 (=101 in binary), so 3 3 3 3 3 turns into 3 5. Your a_i are now 3 5 5 7 9. (Note that this is equivalent to adding numbers in binary, but it's more efficient since you know that your numbers have up to 10^9 bits but at max 10^5 bits are set!)

(3) Repeat step 2 until you no longer have duplicates. In this example you only need another step, you end up with 3 6 7 9.

(4) Calculate max(a_i) - number of a_i left + 1. This is your result, in this case 9-4+1=6.

---

Possible implementation of step (2) :

The first thing I would try is overwriting from the beginning, but keeping a pointer to check where I am at the moment, so: You read 3. You binary search for the last 3 and keep a pointer to the following element. You then overwrite: 3 3 3 3 3 5 7 9 -> 3 5 x x x *5 7 9 (it doesn't matter what's at the x positions, and the pointer is now at the 5). Now, for a first solution, simply copy everything from the end to make it contiguous again: 3 5 5 7 9 and remember that your array is now shorter.

This is not the most efficient solution as it will lead to a lot of copying if you have an array like 3 3 4 4 5 5 6 6..., but it should be decent enough.

For better performance, you could only do step (1) and then insert everything into a hashmap that maps a_i to the number of times it appears, and then operate on that hashmap. That's pretty fast for your constraints, but implementing a hashmap in C isn't trivial.

Answer 2

What you need to do is to work with bit arrays.

You need a_i <= 2*10⁹ (2 billion). To represent 2 billion bits, you need about 256MB of memory (every byte stores 8 bits). You may need to create some convenient abstraction layer that will provide functions like .get(int n), .set(int n) which will read and save bits in that bit array.

---

To allocate array, use malloc:

typedef byte unsigned char;
// 256MB, enough for 2 billion bits
byte * bit_array = malloc(256*1024*1024);

// or use calloc, which initializes to 0:
byte * bit_array = calloc(256*1024*1024, 1);

To set bit n, use this assignment:

bit_array[n/8] |= 1 << (n % 8);

To get bit n, use this expression:

(bit_array[n/8] >> (n % 8)) & 1

---

You algorithm could be something like this:

• Create bit array of desired maximum length all 1 set.
• Loop through all a_i and set i-th bit in that bit array to 0.
• Count how many bits are still set to 1. That is your answer.