# Find Bit Whose Minimum Sequence Flips Makes all Bits Same in Java

In this tutorial, we are going to find bit minimum sequence flips makes all bits same in Java. Given a binary string, our goal is to find a bit such that by flipping its adjacent bits (i.e., changing its value or its neighbor's value). Determine the bit (output might be either 1 or 0) that requires the fewest consecutive sequence flips to make all of the string's bits equal. Here, flipping a substring or 0s or 1s is referred to as a continuous sequence flip. Print the last possible number if both 0s and 1s are possible.

Examples:

Example 1:

Input: str = “00011110001110”
Output:
Explanation: Three consecutive sequences of zeros and two consecutive sequences of ones are present. Thus, flipping one would result in the fewest flips.

Example 2:

Input: str = “010101100011”
Output: 1
Explanation: Because there are the same number of groups of 0s and 1s, and 1 comes in last.

Example 3:

Input: 00010110 3

Output: 3

Explanation

We can convert the given string into all 1s in 3 operations. Operations performed are:

Flip S[0, 2]  (string becomes ‘11110110’).

Flip S[4, 6]  (string becomes ‘11111000’).

Flip S[5, 7]  (string becomes ‘11111111’).

## Naïve approach:

Step 1: Use the variables groupOfZeros and gropupOfOnes to count the groups of 0s and 1s as you begin to traverse the string.

Step 2: Next, contrast the number of one- and zero-group entries. The answer will be that which has the lower count.
Step 2.1: The answer will be the string's final character if both are equal. Please pay close attention to the string.

Step 2.2: If the beginning and last characters in the string are equal, the character at the last index will have more groups in the string. Consequently, a different character will respond.
Step 2.3: There is an equal number of groups for both characters if the first and last characters are not equal. Hence, the character at the last index will provide the solution.

Filename: MinSequence.java

public class MinSequence

{

// The ability to determine which bit needs to be flipped

static char bitToBeFlipped(String str)

{

// variable to hold the string's initial and last character

char lastChar = str.charAt(str.length() - 1);

char firstChar = str.charAt(0);

// Verify that the first and last characters are equal. If they are, return the character that is not at the end.

if (lastChar == firstChar)

{

if (lastChar == '0')

{

return '1';

}

else

{

return '0';

}

}

// else return last

else if (lastChar != firstChar)

{

return lastChar;

}

return lastChar;

}

public static void main(String[] args)

{

String str = "1101011000";

System.out.println(bitToBeFlipped(str));

}

}

Output:

0

Time complexity: The time complexity of a program is O(1).

Space complexity: The space complexity of a program is O(1).

## Approach 1: Using greedy algorithm

### ALGORITHM:

Step 1: Iterate from i = 0 to N-1:

Step 2: Check if S[i] is the same as S[i+1].

Step 2.1: If they are the same then no bit flip is required.

Step 2.2: Otherwise, increment the number of flips by 1.

Step 2.3: After each check move from i to i+2.

Step 2.4: The total number of flips calculated is the required minimum answer.

Filename: MinimumFlips.java

import java.io.*;

import java.util.*;

public class MinimumFlips

{

// A function to determine the minimum number of bit flips

static int solve(String str)

{

// Variable to that stores the fewest flips possible

int number = str.length();

for (int i = 0; i < number; i += 2)

{

if (str.charAt(i) != str.charAt(i+1))

}

}

public static void main(String[] args)

{

String Str = "1110011000";

System.out.print(solve(Str));

}

}

Output:

3

Time complexity: The time complexity of a program is O(n).

Space complexity: The space complexity of a program is O(1).