# 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****:** 1 **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 answer = 0;

int number = str.length();

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

{

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

answer++;

}

// Return the answer

return answer;

}

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).