Minimum flips to make all 1s in left and 0s in right | Set 1 (Using Bitmask)

0 0 6 minutes read

Given a binary array, we can flip all the 1 are in the left part and all the 0 to the right part. Calculate the minimum flips required to make all 1s in left and all 0s in right.

Examples:

Input: 1011000  
Output: 1
1 flip is required to make it 1111000.

Input : 00001 
Output : 2
2 flips required to make it 10000.

For solving this problem we use bitmasking. First, we convert this array to a string, then we find the equivalent decimal number of that binary string. We try all masks with all possibilities of 1s in left and 0s in right. We iterate a loop till the decimal number becomes zero. Each time we will do bitwise XOR of the number with mask and the number of ones in XOR value will be the number of flips required. We decrease n by 1 and update the mask.

Take binary array as input
Convert array to string and then the equivalent decimal number(num)
Take initial mask value and iterate till num <= 0
Find required flips using (num XOR mask)
Find minimum flips and decrease num and update mask
Return the minimum count

Implementation:

C++

// C++ program to find 
// of flips till that 
// all 1s in left
#include <bits/stdc++.h>
using namespace std;
 
int countones(long n);
  
// Function to count minimum 
// number of flips
int findMiniFlip(int nums[], int n)
{
  string s = "";
  for (int i = 0; i < n; i++)
    s += nums[i];
 
  char *end;
  char tmp[s.length()];
  strcpy(tmp, s.c_str()); 
 
  // This is converting string 
  // s into integer of base 2 
  // (if s = '100' then num = 4)
  long num = strtol(tmp, &end, 2);
 
  // Initialize minXor 
  // with n that can be 
  // maximum number of flips
  int minXor = n;
 
  // right shift 1 by (n-1) bits
  long mask = (1 << (n - 1));
  while (n - 1 > 0) 
  {
    // Calculate bitwise 
    // XOR of num and mask
    long temp = (num ^ mask);
 
    // Math.min(a, b) returns 
    // minimum of a and b
    // return minimum number 
    // of flips till that digit
    minXor = min(minXor, countones(temp));
    n--;
    mask = (mask | (1 << (n - 1)));
  }
  return minXor;
}
 
// Function to count number of 1s
int countones(long n)
{
  int c = 0;
  while (n > 0) 
  {
    n = n & (n - 1);
    c++;
  }
  return c;
}
  
// Driver code
int main()
{
  int nums[] = {1, 0, 1, 
                1, 0, 0, 0};
  int size = sizeof(nums) / 
             sizeof(nums[0]);
  int n = findMiniFlip(nums, size);
  cout << n;
}
 
// This code is contributed by Rutvik_56

Java

// Java program to find minimum flips to make
// all 1s in left
import java.io.*;
 
class GFG {
 
    // function to count minimum number of flips
    public static int findMiniFlip(int[] nums)
    {
        int n = nums.length;
        String s = "";
        for (int i = 0; i < n; i++)
            s += nums[i];
 
        // This is converting string s into integer 
        // of base 2 (if s = '100' then num = 4)
        long num = Integer.parseInt(s, 2);
 
        // initialize minXor with n that can be maximum 
        // number of flips
        int minXor = n;
 
        // right shift 1 by (n-1) bits
        long mask = (1 << (n-1));
        while (n-1 > 0) {
 
            // calculate bitwise XOR of num and mask
            long temp = (num ^ mask);
 
            // Math.min(a, b) returns minimum of a and b
            // return minimum number of flips till that 
            // digit
            minXor = Math.min(minXor, countones(temp));
            n--;
 
            mask = (mask | (1 << n -1));
        }
        return minXor;
    }
 
    // function to count number of 1s
    public static int countones(long n)
    {
        int c = 0;
        while (n > 0) {
            n = n & (n-1);
            c++;
        }
        return c;
    }
 
    public static void main(String[] args)
    {
        int[] nums = { 1, 0, 1, 1, 0, 0, 0 };
        int n = findMiniFlip(nums);
        System.out.println(n);
    }
}

Python3

# Python3 program to find minimum flips to make
# all 1s in left
 
# Function to count minimum number of flips
def findMiniFlip(nums):
 
    n = len(nums)
    s = ''
     
    for i in range(n):
        s += str(nums[i])
 
    # This is converting string s into integer
    # of base 2 (if s='100' then num=4)
    num = int(s, 2)
 
    # Initialize minXor with n that can be maximum
    # number of flips
    minXor = n;
 
    # Right shift 1 by(n-1) bits
    mask = (1 << (n - 1))
    while (n - 1 > 0):
 
        # Calculate bitwise XOR of num and mask
        temp = (num ^ mask)
 
        # Math.min(a, b) returns minimum of a and b
        # return minimum number of flips till that
        # digit
        minXor = min(minXor, countones(temp))
        n -= 1
        mask = (mask | (1 << n - 1))
         
    return minXor
     
# Function to count number of 1s
def countones(n):
     
    c = 0
    while (n > 0):
        n = n & (n - 1)
        c += 1
         
    return c
 
# Driver code
if __name__ == "__main__":
 
    nums = [ 1, 0, 1, 1, 0, 0, 0 ]
    n = findMiniFlip(nums)
     
    print(n)
 
# This code is contributed by chitranayal

C#

// C# program to find 
// minimum flips to make
// all 1s in left
using System;
class GFG{
 
// Function to count minimum 
// number of flips
public static int findMiniFlip(int[] nums)
{
  int n = nums.Length;
  String s = "";
  for (int i = 0; i < n; i++)
    s += nums[i];
 
  // This is converting string 
  // s into integer of base 2
  // (if s = '100' then num = 4)
  long num = Convert.ToInt32(s, 2);
 
  // initialize minXor with n 
  // that can be maximum 
  // number of flips
  int minXor = n;
 
  // right shift 1 by (n-1) bits
  long mask = (1 << (n - 1));
  while (n - 1 > 0) 
  {
    // calculate bitwise XOR 
    // of num and mask
    long temp = (num ^ mask);
 
    // Math.Min(a, b) returns 
    // minimum of a and b
    // return minimum number 
    // of flips till that 
    // digit
    minXor = Math.Min(minXor, 
                      countones(temp));
    n--;
    mask = (mask | (1 << n - 1));
  }
  return minXor;
}
 
// Function to count number of 1s
public static int countones(long n)
{
  int c = 0;
  while (n > 0) 
  {
    n = n & (n - 1);
    c++;
  }
  return c;
}
 
// Driver code
public static void Main(String[] args)
{
  int[] nums = {1, 0, 1, 1, 
                0, 0, 0};
  int n = findMiniFlip(nums);
  Console.WriteLine(n);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// JavaScript program to find minimum 
// flips to make all 1s in left
 
// Function to count minimum number of flips
function findMiniFlip(nums)
{
    let n = nums.length;
    let s = "";
    for(let i = 0; i < n; i++)
        s += nums[i];
 
    // This is converting string s into integer
    // of base 2 (if s = '100' then num = 4)
    let num = parseInt(s, 2);
 
    // Initialize minXor with n that 
    // can be maximum number of flips
    let minXor = n;
 
    // Right shift 1 by (n-1) bits
    let mask = (1 << (n - 1));
    while (n - 1 > 0)
    {
         
        // Calculate bitwise XOR of num and mask
        let temp = (num ^ mask);
 
        // Math.min(a, b) returns minimum of a and b
        // return minimum number of flips till that
        // digit
        minXor = Math.min(minXor, countones(temp));
        n--;
 
        mask = (mask | (1 << n -1));
    }
    return minXor;
}
 
// Function to count number of 1s
function countones(n)
{
    let c = 0;
    while (n > 0) 
    {
        n = n & (n - 1);
        c++;
    }
    return c;
}
 
// Driver Code
let nums = [ 1, 0, 1, 1, 0, 0, 0 ];
let n = findMiniFlip(nums);
 
document.write(n);
 
// This code is contributed by code_hunt
 
</script>

Output:

Time Complexity: O(n)
Space Complexity: O(n)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!