# Minimum Number of Flips

In this article, we are going to see how to solve the following flipping problem on forming a binary string? This problem has been featured in Goldman Sachs interview round.
Submitted by Radib Kar, on March 07, 2019

Problem statement:

Given a binary string (containing only 0s and 1s). We need to make this string a sequence of alternate characters (0 and 1) by flipping some of the bits, our goal is to minimize the number of bits to be flipped. Write a program to determine the minimum number of bits to reach the goal.

Examples:

```    Input:
0000 (binary string)
Output:
2

Input:
110 (binary string)
Output:
1
```

Example explanations:

```    Input:
0000
Output strings possible from the input string,
which satisfies the constraints:
0101
1010
Both strings are valid and both require 2 bits to be flipped.
Thus minimum no of flipping needed is 2

Input:
110
Output strings possible from the input string,
which satisfies the constraints:
010
101
The first one needs only one flips
While the second one need two flips
Hence minimum flip required is 1
```

Solution:

Observation reveals that the converted string can be of two types:

1. Starts with a 0
2. Starts with a 1

What we need to do is to convert the input string into both of this two category. Calculate corresponding flips needed to convert. Return the minimum flips.

Pre-requisite:

Input string s

Algorithm:

1) Declare variables and initialize like below.

```    flip0 = 0, flip1 = 0, flag0 = 0, flag1 = 1
flip0=number of flips needed when converted string starts with 0
flip1=number of flips needed when converted string starts with 1
flag0=the current character value that should be at current string index,
incase converted string starts from 0, value changes from 0 to 1,
1 to 0 alternatively
flag1 = the current character value that should be at current string index,
incase converted string starts from 1,
value changes from 0 to 1, 1 to 0 alternatively
```

2) Count number of flips needed for converting input string to the valid string starting with 0

```    for i=0:s.length()-1
iF (flag0 != s[i]-'0')
flip0++;
END IF
flag0=1-flag0;
END FOR
```

3) Count number of flips needed for converting input string to the valid string starting with 1

```    for i=0:s.length()-1
iF (flag1 != s[i]-'0')
flip1++;
END IF
flag1=1-flag1;
END FOR
```

4) return minimum of flip0 and flip1;

C++ implementation

```#include <bits/stdc++.h>
using namespace std;

void print(vector<int> a,int n){
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}

int minflip(string s)
{
int flip0=0,flip1=0,flag0=0,flag1=1;

//converting to string starting with 0
for(int i=0;i<s.length();i++){
if(flag0!=s[i]-'0')
flip0++;
flag0=1-flag0;
}

//converting to string starting with 1
for(int i=0;i<s.length();i++){
if(flag1!=s[i]-'0')
flip1++;
flag1=1-flag1;
}

return flip0>flip1?flip1:flip0; //returnig minimum
}

int main()
{
string s;

cout<<"Enter input string\n";
cin>>s;

cout<<"minimum no of flip required is: "<<minflip(s)<<endl;

return 0;
}
```

Output

```First run:
Enter input string
0000
minimum no of flip required is: 2

Second run:
Enter input string
110
minimum no of flip required is: 1
```

TOP Interview Coding Problems/Challenges

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates