Given two integers N and M denoting the size of an array and the sum of the elements of the array, the task is to find the maximum possible count of total set bits of all the elements of the array such that the sum of the elements is M.
Examples:
Input: N = 1, M = 15
Output: 4
Explanation: Since N =1, 15 is the only possible solution.
The binary representation of 15 is (1111)2 which has 4 set bits.Input: N = 2, M = 11
Output: 4
Explanation: There can be various options for the vector of size 2 and sum 11.
For example: [1, 10] this will give the set bits as 1 + 2 = 3
as their binary representations are 1 and 1010 respectively.
Similarly [2, 9] and [3, 8] will also give 3 set bits
as their binary representations are [10, 1001] and [11, 1000] respectively.
For [4, 7] the set bits will be maximum as
4 is represented by 100 and 7 is represented by 111.
So the total count of set bits = 1 + 3 =4.
Similarly [5, 6] is also a possible solution which gives sum of set bits 4.
For any other options the sum of set bits is always less than 4.
Hence the maximum number of set bits achieved is 4.
Approach: This problem can be solved by the concept of parity and greedy approach based on the following idea:
To maximize the set bit it is optimal to choose as small numbers as possible and set as many bits in each position as possible.
- Put as many 1s as feasible at the current bit for each bit from lowest to highest.
- However, if the parity of M and N differs, we won’t be able to put N 1s on that bit since we won’t be able to achieve M as the sum no matter how we set the upper bits.
- Hence we find out the minimum of N and M (say cur) and then compare the parity of cur and M.
If their parity is different we decrease the cur value by 1 to match the parity of M and set that many bits to 1.Then adjust the sum M, by dividing it by 2 (For easy calculation in next step. We will only need to check the rightmost position and each set bit will contribute 1 to the sum) and repeat this till M becomes 0.
Follow the below illustration for a better understanding:
Illustration:
Consider N = 2 and M = 11.
1st Step:
=> Minimum of 2 and 11 = 2. So cur = 2
=> cur is even and M is odd. Decrease cur by 1. So cur = 2 – 1 = 1.
=> Set 1 bit. So, M = 10, ans = 1.
=> Change M = M/2 =2nd Step:
=> Minimum of 2 and 5 = 2. So cur = 2
=> cur is even and M is odd. Decrease cur by 1. So cur = 2 – 1 = 1.
=> Set 1 bits. So, M = 5 – 1 = 4, ans = 1 + 1 = 2.
=> Set M = 4/2 = 2.3rd Step:
=> Minimum of 2 and 2 = 2. So cur = 2
=> cur is even and M is also even.
=> Set 2 bits. So, M = 2 – 2 = 0, ans = 2 + 2 = 4.
=> Set M = 0/2 = 0.
Follow the below steps to implement the approach:
- Initialize variables to store minimum in each step and the answer.
- Iterate a loop till M is greater than 0:
- Find the minimum of M and N.
- Find the number of bits to be set using the above observation.
- Adjust the M accordingly as mentioned above.
- Add the count of bits set in this stage.
- At the end return the total count of bits as the required answer.
Below is the implementation of the above approach:
C++
|
|
Time Complexity: O(log M)
Auxiliary Space: O(1)
