Bit Toggling to Minimize Array Sum - Coding

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

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[].
Sort the smallestUnsetBit[] array.
Iterate over the smallestUnsetBit[] for T time and calculate the value for smallestUnsetBit[i] by 2^{smallestUnsetBit[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);

Output

Time Complexity: O(N), where N is the length of the given array
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Bit Magic

Related
Maximum commulative XOR of elements with their indices
Count valid Bitwise operation combinations for Binary Strings
Maximum XOR of Two Binary Numbers after shuffling their bits.
Largest number less than equal to N having exactly K set bits
Maximize score of Binary Matrix by Flipping a row or column each time

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	15