Decrease the Array sum by inverting 0 bit Okay instances


View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Given an array arr[] of measurement N and an integer Okay, the duty is to invert the 0 bit (unset bit) of any integer of given array complete Okay instances, such that the general sum of arr will get minimized.

Examples:

Enter: arr = {3, 7, 3}, Okay = 2
Output: 21
Rationalization: Binary illustration 3 is 11, and seven is 111. 
Since we have to set 2 bits, we will set the bottom unset bits 
of the 2 3s such that they develop into 111. 
The entire sum is then 7 + 7 + 7 = 21.

Enter: arr = {2, 3, 4}, Okay = 2
Output: 11

An Strategy utilizing a Grasping algorithm:

The thought of fixing this downside will be accomplished through the use of the grasping approach. We’ll change the rightmost 0s to 1s.

Observe the steps under to implement the above concept:

  • Iterate over the weather of the array.
  • Convert the ingredient into its binary illustration and iterate over the bits of binary illustration.
    • Examine for its ith bit is unset or not.
      • If the ith bit is unset then, Push the ith place into the array smallestUnsetBit.
  • Type the smallestUnsetBit array.
  • Iterate over the smallestUnsetBit for Okay time and calculate the worth for smallestUnsetBit[i] by 2smallestUnsetBit[i], this worth will contribute into the general sum after inverting smallestUnsetBit[i] bit.
  • Return the outcome.

Under is the implementation of the above method:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

#outline mod (1e9 + 7)

  

int minSum(vector<int>& nums, int ok)

{

    vector<int> smallestUnsetBit;

  

    

    

    for (auto num : nums) {

  

        

        

        string s = bitset<31>(num).to_string();

        for (int i = 30; i >= 0; i--) {

  

            

            

            if (s[i] == '0') {

  

                

                

                smallestUnsetBit.push_back(30 - i);

            }

        }

    }

  

    

    

    type(smallestUnsetBit.start(),

         smallestUnsetBit.finish());

  

    

    

    lengthy lengthy outcome

        = accumulate(nums.start(), nums.finish(), 0LL);

  

    int i = 0;

  

    

    

    whereas (k--) {

        outcome

            = (outcome

               + (lengthy lengthy)pow(2, smallestUnsetBit[i++]))

              % (lengthy lengthy)mod;

    }

  

    

    return outcome % (lengthy lengthy)mod;

}

  

int principal()

{

    vector<int> arr = { 3, 7, 3 };

    int Okay = 2;

  

    

    int outcome = minSum(arr, Okay);

    cout << outcome << endl;

    return 0;

}

Time Complexity: O(N), the place N is the size of the given array
Auxiliary Area: O(N)

Leave a Reply