Given an array arr[] consisting of N positive integers, the task is to find the minimum number of bits of array elements required to be flipped to make all array elements equal.
Examples:
Input: arr[] = {3, 5}
Output: 2
Explanation:
Following are the flipping of bits of the array elements required:
- For element arr[0](= 3): Flipping the 3rd bit from the right modifies arr[0] to (= 7(111)2). Now, the array becomes {7, 5}.
- For element arr[0](= 7): Flipping the 2nd bit from the right modifies arr[0] to 5 (= (101)2). Now, the array becomes {5, 5}.
After performing the above operations, all the array elements are equal. Therefore, the total number of flips of bits required is 2.
Input: arr[] = {4, 6, 3, 4, 5}
Output: 5
Â
Approach: The given problem can be solved by modifying the array element in such a way that the number of set bits and unset bits at every position between all array elements. Follow the below steps to solve the problem:
- Initialize two frequency arrays say fre0[] and fre1[] of size 32 for counting the frequency of 0 and 1 for every bit of array elements.
- Traverse the given array and for each array element, arr[i] if the jth bit of arr[i] is a set bit, then increment the frequency of fre1[j] by 1. Otherwise, increment the frequency of fre0[j] by 1.
- After completing the above steps, print the sum of the minimum of fre0[i] and fre1[i] for each bit i over the range [0, 32].
Below is the implementation of the above approach:
C++
// C++ program for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to count minimum number// of bits required to be flipped// to make all array elements equalint makeEqual(int* arr, int n){    // Stores the count of unset bits    int fre0[33] = { 0 };Â
    // Stores the count of set bits    int fre1[33] = { 0 };Â
    // Traverse the array    for (int i = 0; i < n; i++) {Â
        int x = arr[i];Â
        // Traverse the bit of arr[i]        for (int j = 0; j < 33; j++) {Â
            // If current bit is set            if (x & 1) {Â
                // Increment fre1[j]                fre1[j] += 1;            }Â
            // Otherwise            else {Â
                // Increment fre0[j]                fre0[j] += 1;            }Â
            // Right shift x by 1            x = x >> 1;        }    }Â
    // Stores the count of total moves    int ans = 0;Â
    // Traverse the range [0, 32]    for (int i = 0; i < 33; i++) {Â
        // Update the value of ans        ans += min(fre0[i], fre1[i]);    }Â
    // Return the minimum number of    // flips required    return ans;}Â
// Driver Codeint main(){Â Â Â Â int arr[] = { 3, 5 };Â Â Â Â int N = sizeof(arr) / sizeof(arr[0]);Â Â Â Â cout << makeEqual(arr, N);Â
    return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;Â
class GFG{Â
// Function to count minimum number// of bits required to be flipped// to make all array elements equalstatic int makeEqual(int arr[], int n){         // Stores the count of unset bits    int fre0[] = new int[33];Â
    // Stores the count of set bits    int fre1[] = new int[33];Â
    // Traverse the array    for(int i = 0; i < n; i++)    {        int x = arr[i];Â
        // Traverse the bit of arr[i]        for(int j = 0; j < 33; j++)         {Â
            // If current bit is set            if ((x & 1) != 0)             {                                 // Increment fre1[j]                fre1[j] += 1;            }Â
            // Otherwise            else            {                                 // Increment fre0[j]                fre0[j] += 1;            }Â
            // Right shift x by 1            x = x >> 1;        }    }Â
    // Stores the count of total moves    int ans = 0;Â
    // Traverse the range [0, 32]    for(int i = 0; i < 33; i++)    {                 // Update the value of ans        ans += Math.min(fre0[i], fre1[i]);    }Â
    // Return the minimum number of    // flips required    return ans;}Â
// Driver Codepublic static void main(String[] args){Â Â Â Â int arr[] = { 3, 5 };Â Â Â Â int N = arr.length;Â Â Â Â Â Â Â Â Â System.out.print(makeEqual(arr, N));}}Â
// This code is contributed by Kingash |
Python3
# Python3 program for the above approachÂ
# Function to count minimum number# of bits required to be flipped# to make all array elements equaldef makeEqual(arr, n):       # Stores the count of unset bits    fre0 = [0]*33Â
    # Stores the count of set bits    fre1 = [0]*33         # Traverse the array    for i in range(n):Â
        x = arr[i]Â
        # Traverse the bit of arr[i]        for j in range(33):Â
            # If current bit is set            if (x & 1):                # Increment fre1[j]                fre1[j] += 1            # Otherwise            else:                # Increment fre0[j]                fre0[j] += 1            # Right shift x by 1            x = x >> 1Â
    # Stores the count of total moves    ans = 0Â
    # Traverse the range [0, 32]    for i in range(33):               # Update the value of ans        ans += min(fre0[i], fre1[i])Â
    # Return the minimum number of    # flips required    return ansÂ
# Driver Codeif __name__ == '__main__':Â Â Â Â arr= [3, 5]Â Â Â Â N = len(arr)Â Â Â Â print(makeEqual(arr, N))Â
# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG {Â
    // Function to count minimum number    // of bits required to be flipped    // to make all array elements equal    static int makeEqual(int[] arr, int n)    {Â
        // Stores the count of unset bits        int[] fre0 = new int[33];Â
        // Stores the count of set bits        int[] fre1 = new int[33];Â
        // Traverse the array        for (int i = 0; i < n; i++) {            int x = arr[i];Â
            // Traverse the bit of arr[i]            for (int j = 0; j < 33; j++) {Â
                // If current bit is set                if ((x & 1) != 0) {Â
                    // Increment fre1[j]                    fre1[j] += 1;                }Â
                // Otherwise                else {Â
                    // Increment fre0[j]                    fre0[j] += 1;                }Â
                // Right shift x by 1                x = x >> 1;            }        }Â
        // Stores the count of total moves        int ans = 0;Â
        // Traverse the range [0, 32]        for (int i = 0; i < 33; i++) {Â
            // Update the value of ans            ans += Math.Min(fre0[i], fre1[i]);        }Â
        // Return the minimum number of        // flips required        return ans;    }Â
    // Driver Code    public static void Main()    {        int[] arr = { 3, 5 };        int N = arr.Length;Â
        Console.WriteLine(makeEqual(arr, N));    }}Â
// This code is contributed by ukasp. |
Javascript
<script>// javascript program for the above approach    // Function to count minimum number    // of bits required to be flipped    // to make all array elements equal    function makeEqual(arr , n)    {Â
        // Stores the count of unset bits        var fre0 = Array(33).fill(0);Â
        // Stores the count of set bits        var fre1 = Array(33).fill(0);Â
        // Traverse the array        for (i = 0; i < n; i++) {            var x = arr[i];Â
            // Traverse the bit of arr[i]            for (j = 0; j < 33; j++) {Â
                // If current bit is set                if ((x & 1) != 0) {Â
                    // Increment fre1[j]                    fre1[j] += 1;                }Â
                // Otherwise                else {Â
                    // Increment fre0[j]                    fre0[j] += 1;                }Â
                // Right shift x by 1                x = x >> 1;            }        }Â
        // Stores the count of total moves        var ans = 0;Â
        // Traverse the range [0, 32]        for (i = 0; i < 33; i++) {Â
            // Update the value of ans            ans += Math.min(fre0[i], fre1[i]);        }Â
        // Return the minimum number of        // flips required        return ans;    }Â
    // Driver Code        var arr = [ 3, 5 ];        var N = arr.length;Â
        document.write(makeEqual(arr, N));Â
// This code is contributed by aashish1995</script> |
Output:Â
2
Â
Time Complexity: O(N * log N)Â
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
