Bit Toggling to Minimize Array Sum Using Greedy Technique
We can use the greedy technique here, we’ll change the rightmost 0s to 1s.
Step-by-step approach:
- Iterate over the elements of the array and count the total set bit T.
- Again, Iterate over the elements of the array
- Convert the element into its binary representation and iterate over the bits of binary representation.
- Check for its ith bit is unset or not.
- If the ith bit is unset then, Push the ith position into the array smallestUnsetBit[].
- Convert the element into its binary representation and iterate over the bits of binary representation.
- Sort the smallestUnsetBit[] array.
- Iterate over the smallestUnsetBit[] for T time and calculate the value for smallestUnsetBit[i] by 2smallestUnsetBit[i] , this value will contribute into the overallSum after toggling smallestUnsetBit[i] bit.
- Return the overallSum.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach: #include <bits/stdc++.h> using namespace std; #define mod (1e9 + 7) // Function to find the minimum sum int minSum(vector< int >& nums) { int T = 0; // find the total number of set bit. for ( int i : nums) { T += __builtin_popcount(i); } vector< int > smallestUnsetBit; // Iterate over the elements of // given array for ( auto num : nums) { // Converting the number to its // binary representation string s = bitset<31>(num).to_string(); for ( int i = 30; i >= 0; i--) { // Check if the ith bit is // unset of not if (s[i] == '0' ) { // Push ith unset bit // into smallestUnsetBit smallestUnsetBit.push_back(30 - i); } } } // Sort the usetbits in // ascending order. sort(smallestUnsetBit.begin(), smallestUnsetBit.end()); // Calculate the overall sum // of given array long long result = accumulate(nums.begin(), nums.end(), 0LL); int i = 0; // Add the overall effect of sum in // the result by inverting the '0' bits. while (T--) { result = (result + ( long long ) pow (2, smallestUnsetBit[i++])) % ( long long )mod; } // Return the result return result % ( long long )mod; } // Driver function int main() { vector< int > arr = { 2, 2, 2 }; // Function call int result = minSum(arr); cout << result << endl; return 0; } |
Java
// Java code to implement the approach import java.util.*; import java.util.stream.*; public class Main { static final int MOD = ( int )1e9 + 7 ; public static int minSum(List<Integer> nums) { int T = 0 ; // Find the total number of set bits. for ( int i : nums) { T += Integer.bitCount(i); } List<Integer> smallestUnsetBit = new ArrayList<>(); // Iterate over the elements of the given list for ( int num : nums) { // Converting the number to its binary // representation String s = String .format( "%31s" , Integer.toBinaryString(num)) .replace( ' ' , '0' ); for ( int i = 30 ; i >= 0 ; i--) { // Check if the ith bit is unset or not if (s.charAt(i) == '0' ) { // Push the ith unset bit into // smallestUnsetBit smallestUnsetBit.add( 30 - i); } } } // Sort the unset bits in ascending order Collections.sort(smallestUnsetBit); // Calculate the overall sum of the given list long result = nums.stream() .mapToLong(Integer::longValue) .sum(); int i = 0 ; // Add the overall effect of sum by inverting the // '0' bits for ( int j = 0 ; j < T; j++) { result = (result + ( long )Math.pow( 2 , smallestUnsetBit.get(i++))) % MOD; } // Return the result return ( int )(result % MOD); } public static void main(String[] args) { List<Integer> arr = Arrays.asList( 2 , 2 , 2 ); // Function call int result = minSum(arr); System.out.println(result); } } // This code is contributed by Abhinav Mahajan // (abhinav_m22). |
Python3
def minSum(nums): mod = int ( 1e9 + 7 ) T = 0 # Find the total number of set bits. for num in nums: T + = bin (num).count( '1' ) smallestUnsetBit = [] # Iterate over the elements of the given array for num in nums: # Converting the number to its binary representation s = format (num, '031b' ) for i in range ( 30 , - 1 , - 1 ): # Check if the ith bit is unset or not if s[i] = = '0' : # Push the ith unset bit into smallestUnsetBit smallestUnsetBit.append( 30 - i) # Sort the unset bits in ascending order smallestUnsetBit.sort() # Calculate the overall sum of the given array result = sum (nums) i = 0 # Add the overall effect of sum by inverting the '0' bits while T > 0 : result = (result + 2 * * smallestUnsetBit[i]) % mod i + = 1 T - = 1 # Return the result return result % mod # Driver function if __name__ = = "__main__" : arr = [ 2 , 2 , 2 ] # Function call result = minSum(arr) print (result) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static int Mod = 1000000007; // Function to find the minimum sum static int MinSum(List< int > nums) { int T = 0; // find the total number of set bit. foreach ( int num in nums) { T += BitCount(num); } List< int > smallestUnsetBit = new List< int >(); // Iterate over the elements of given array foreach ( var num in nums) { // Converting the number to its binary representation string s = Convert.ToString(num, 2).PadLeft(31, '0' ); for ( int j = 30; j >= 0; j--) { // Check if the jth bit is unset or not if (s[j] == '0' ) { // Push jth unset bit into smallestUnsetBit smallestUnsetBit.Add(30 - j); } } } // Sort the unset bits in ascending order. smallestUnsetBit.Sort(); // Calculate the overall sum of given array long result = nums.Sum(x => ( long )x); int index = 0; // Add the overall effect of sum in the result by inverting the '0' bits. while (T-- > 0) { result = (result + ( long )Math.Pow(2, smallestUnsetBit[index++])) % Mod; } // Return the result return ( int )(result % Mod); } // Helper function to count set bits static int BitCount( int n) { int count = 0; while (n > 0) { n &= (n - 1); count++; } return count; } // Driver function static void Main( string [] args) { List< int > arr = new List< int > { 2, 2, 2 }; // Function call int result = MinSum(arr); Console.WriteLine(result); } } |
Javascript
const mod = 1e9 + 7; // Function to find the minimum sum function minSum(nums) { let T = 0; // find the total number of set bits for (let i of nums) { T += i.toString(2).split( '1' ).length - 1; } let smallestUnsetBit = []; // Iterate over the elements of given array for (let num of nums) { // Converting the number to its binary representation let s = num.toString(2).padStart(31, '0' ); for (let i = 30; i >= 0; i--) { // Check if the ith bit is unset or not if (s[i] === '0' ) { // Push ith unset bit into smallestUnsetBit smallestUnsetBit.push(30 - i); } } } // Sort the unset bits in ascending order smallestUnsetBit.sort((a, b) => a - b); // Calculate the overall sum of given array let result = nums.reduce((acc, curr) => acc + curr, 0); let i = 0; // Add the overall effect of sum by inverting the '0' bits while (T--) { result = (result + 2 ** smallestUnsetBit[i++]) % mod; } // Return the result return result % mod; } // Driver code let arr = [2, 2, 2]; // Function call let result = minSum(arr); console.log(result); |
9
Time Complexity: O(N), where N is the length of the given array
Auxiliary Space: O(N)
Bit Toggling to Minimize Array Sum
Given an array arr[] consisting of positive integers of size N. the task is to minimize the overall sum of arr[] by toggling the unset bit (0 bit) of any element of the array for T times, where T is the total number of set bits over all the elements of arr[].
Note: In case of 32-bit integer overflow, return (overall Sum % 1e9 + 7).
Examples:
Input: arr = {2, 2, 2};
Output: 21
Explanation: Binary representation 2 is 10. Since there are total 3 set bit. so, we need to set 3 bits, we can set the lowest unset bits of the every 2s such that they become 11. The total sum is then 3 + 3 + 3 = 9.Input: arr = {3, 3, 7}
Output: 77