Maximize complete set bits of parts in N sized Array with sum M

Given two integers N and M denoting the dimensions of an array and the sum of the weather of the array, the duty is to seek out the utmost doable depend of complete set bits of all the weather of the array such that the sum of the weather is M.

Examples:

Enter: N = 1, M = 15
Output: 4
Clarification: Since N =1, 15 is the one doable answer. 
The binary illustration of 15 is (1111)₂ which has 4 set bits.

Enter: N = 2, M = 11
Output: 4
Clarification: There could be varied choices for the vector of measurement 2 and sum 11.
For instance: [1, 10] this may give the set bits as 1 + 2 = 3 
as their binary representations are 1 and 1010 respectively.
Equally [2, 9] and [3, 8] will even give 3 set bits 
as their binary representations are [10, 1001] and [11, 1000] respectively.
For [4, 7] the set bits might be most as 
4 is represented by 100 and seven is represented by 111.
So the full depend of set bits = 1 + 3 =4.
Equally [5, 6] can be a doable answer which provides sum of set bits 4.
For every other choices the sum of set bits is at all times lower than 4. 
Therefore the utmost variety of set bits achieved is 4.

Method: This downside could be solved by the idea of parity and grasping strategy based mostly on the next concept:

To maximise the set bit it’s optimum to decide on as small numbers as doable and set as many bits in every place as doable.

• Put as many 1s as possible on the present bit for every bit from lowest to highest. 
• Nonetheless, if the parity of M and N differs, we gained’t be capable of put N 1s on that bit since we gained’t be capable of obtain M because the sum regardless of how we set the higher bits. 
• Therefore we discover out the minimal of N and M (say cur) after which examine the parity of cur and M. 
  If their parity is totally different we lower the cur worth by 1 to match the parity of M and set that many bits to 1.

Then regulate the sum M, by dividing it by 2 (For simple calculation in subsequent step. We are going to solely have to test the rightmost place and every set bit will contribute 1 to the sum) and repeat this until M turns into 0.

Comply with the beneath illustration for a greater understanding:

Illustration:

Think about N = 2 and M = 11.

1st Step:
        => Minimal of two and 11 = 2. So cur = 2
        => cur is even and M is odd. Lower cur by 1. So cur = 2 – 1 = 1.
        => Set 1 bit. So, M = 10, ans = 1.
        => Change M = M/2 = 

2nd Step:
        => Minimal of two and 5 = 2. So cur = 2
        => cur is even and M is odd. Lower 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.

third Step:
        => Minimal of two and a pair of = 2. So cur = 2
        => cur is even and M can be even.
        => Set 2 bits. So, M = 2 – 2 = 0, ans = 2 + 2 = 4.
        => Set M = 0/2 = 0.

Comply with the beneath steps to implement the strategy:

• Initialize variables to retailer minimal in every step and the reply.
• Iterate a loop until M is larger than 0:
  • Discover the minimal of M and N.
  • Discover the variety of bits to be set utilizing the above remark.
  • Regulate the M accordingly as talked about above.
  • Add the depend of bits set on this stage.
• On the finish return the full depend of bits because the required reply.

Beneath is the implementation of the above strategy:

Time Complexity: O(log M)
Auxiliary Area: O(1)