Home » Interview coding problems/challenges

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 [Last updated : March 20, 2023]

Problem Description

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 of Minimum Number of Flips

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 of Minimum Number of Flips

#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