Minimum flips to make all 1 s in left and 0 s in right | Set 1 ( Using Bitmask ) | C ++ program to find of flips till that all 1 s in lef ; Function to count minimum number of flips ; This is converting string s into integer of base 2 ( if s = '100' then num = 4 ) ; Initialize minXor with n that can be maximum number of flips ; right shift 1 by ( n - 1 ) bits ; Calculate bitwise XOR of num and mask ; Math . min ( a , b ) returns minimum of a and b return minimum number of flips till that digit ; Function to count number of 1 s ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countones ( long n ) ; 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 ( ) ) ; long num = strtol ( tmp , & end , 2 ) ; int minXor = n ; long mask = ( 1 << ( n - 1 ) ) ; while ( n - 1 > 0 ) { long temp = ( num ^ mask ) ; minXor = min ( minXor , countones ( temp ) ) ; n -- ; mask = ( mask | ( 1 << ( n - 1 ) ) ) ; } return minXor ; } int countones ( long n ) { int c = 0 ; while ( n > 0 ) { n = n & ( n - 1 ) ; c ++ ; } return c ; } 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 ; }