New update is available. Click here to update.

Last Updated: 3 Feb, 2021

Difficulty: Easy

```
Minimum operations to make ‘STR’ ‘0010’ beautiful is ‘1’. In one operation, we can convert ‘0’ at index ‘0’ (0-based indexing) to ‘1’. The ‘STR’ now becomes ‘1010’ which is a beautiful string.
```

```
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The only line of each test case contains a binary string 'STR'.
```

```
For each test case, print the minimum operations needed to make ‘STR’ beautiful.
Print the output of each test case in a separate line.
```

```
You are not required to print the expected output, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
2 <= |STR| <= 10^5
STR[i] = ‘1’ or ‘0’
Where '|STR|' denotes the length of ‘STR’.
Time Limit: 1 sec
```

We observe that for any length of the given string ‘STR’, there are only two possible beautiful strings ie: one starting with ‘1’ and the other starting with ‘0’.

For example for ‘*N’ *= 4 , “1010” and “0101” are the only two possible beautiful strings.

Now, we just need to count the different values at the same index in a possible beautiful string and given ’STR’.

For example: If ‘*STR’ *= “1011”, there exist two beautiful strings of length 4 ie: “1010” and “0101”. The count of different values at same index in ‘*STR*’ and “1010” is 1 and ‘*STR*’ and “0101” is 3 respectively and 1 is the minimum of these two so we need only ‘1’ operation to convert ‘1011’ to ‘1010’.

**Algorithm:**

Initialize four variables ‘*T1’ *= 0, ‘*T2’ *= 0,’*S1’ *= 0’ and ‘*S2’* = 1 where ‘*T1*’ denotes the difference between values at indices in ‘*STR*’ and the possible beautiful string starting with 0 and ‘*T2*’ denotes the difference between values at indices in ‘*STR’* and the possible beautiful string starting with 1.‘*S1’ *and ‘*S2*’ denote the expected value at index ‘*i*’ in both of the possible beautiful strings

Iterate the given string ‘*STR’* and do the following:

- If ‘
*STR[i]’*== 1- If ‘
*S1’*== 0’ then*T1++*. - Else
*T2++*.

- If ‘
- If ‘
*STR[i]’*== 0- If ‘
*S1’*== 1 then*T1++*. - Else
*T2++*

- If ‘
- If ‘
*S1’*== 0’*S2*’. - Finally return the minimum of ‘
*T1*’ and ‘*T2*’.

SIMILAR PROBLEMS

Divisible Substrings

Posted: 29 Jul, 2022

Difficulty: Easy

Ninja and Numbers

Posted: 30 Jul, 2022

Difficulty: Moderate

Longest Palindromic Substring

Posted: 4 Sep, 2022

Difficulty: Moderate

Cakes

Posted: 23 Sep, 2022

Difficulty: Easy

1-3 Palindrome

Posted: 4 Oct, 2022

Difficulty: Easy

Popular Interview Problems: