LeetCode 3750 - Minimum Number of Flips to Reverse Binary String

LeetCode Problem 3750

Difficulty: 🟢 Easy
Topics: Math, Two Pointers, String, Bit Manipulation

Solution

Problem Understanding

The problem gives us a positive integer n, and asks us to work with its binary representation. First, we convert n into a binary string s without leading zeros. Then, we compute the reverse of that binary string. Our goal is to determine the minimum number of bit flips required so that s becomes equal to its reversed version.

A flip means changing exactly one bit: 0 → 1 or 1 → 0. Every flip only affects one position in the binary string.

It is important to interpret the problem carefully. We are not trying to make the binary string a palindrome. Instead, we want to transform s into the reverse of the original string. The reversed string is fixed and does not change as we flip bits.

For example:

• If n = 7, its binary representation is "111". Reversing it gives "111", which is already identical to the original string. Therefore, zero flips are required.
• If n = 10, its binary representation is "1010". Reversing it gives "0101". Since every bit differs between the two strings, we must flip all four positions.

The constraint 1 <= n <= 10^9 tells us that the binary representation will be at most about 30 bits long, because 2^30 ≈ 10^9. This means the input size is extremely small, so even relatively inefficient string operations are acceptable. However, we should still aim for a clean and efficient solution.

Several edge cases are worth identifying early:

• A single-bit binary number such as n = 1 ("1") always requires 0 flips because reversing a single character produces the same string.
• Binary strings that are already equal to their reverse, such as "111" or "1001", require no flips.
• Binary strings where every position differs from the reverse, such as "1010" versus "0101", require flipping every bit.
• Odd-length strings have a middle character that maps to itself in the reverse, so that position never contributes to the answer.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to explicitly construct the reversed binary string and compare it against the original string character by character.

We first convert n into binary form, then create its reverse. After that, we iterate through both strings simultaneously and count how many positions contain different bits. Since one flip fixes one mismatched position, the number of mismatches is exactly the minimum number of flips required.

This approach is correct because each bit position in s corresponds to a fixed target bit in the reversed string. If a bit already matches, no action is needed. If it differs, we must flip it exactly once. Since every position is independent, counting mismatches gives the optimal answer.

Although this method is already efficient enough due to the small input size, it uses extra space to store the reversed string.

Optimal Approach

We can improve slightly by avoiding construction of the reversed string altogether.

The key observation is that the reverse relationship simply pairs positions from opposite ends of the binary string. Instead of explicitly building the reversed string, we can compare characters using two pointers:

• One pointer starts at the beginning.
• The other pointer starts at the end.

At each step, we compare s[left] with s[right].

Since the reversed string places s[right] at position left, if these two values differ, then position left in the original string does not match what it should be in the reversed version. Likewise, position right also mismatches.

Each mismatch pair contributes 2 flips, because both positions must be changed to match the reversed target string.

For example:

s = "1010"
reverse = "0101"

index:    0 1 2 3
s:        1 0 1 0
reverse:  0 1 0 1

Pair (0,3) differs, contributing 2 flips. Pair (1,2) differs, contributing another 2. Total = 4.

This avoids building an extra reversed string and only scans half the binary representation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k)	O(k)	Build reversed string and count mismatches
Optimal	O(k)	O(1)	Two pointers compare mirrored positions directly

Here, k is the number of bits in the binary representation of n.

Algorithm Walkthrough

1. Convert the integer n into its binary representation without the "0b" prefix. In Python, this can be done with bin(n)[2:]. This gives us the string s.
2. Initialize two pointers:

• left = 0, pointing to the start of the string.
• right = len(s) - 1, pointing to the end.

3. Initialize a variable flips = 0 to store the total number of required flips.
4. While left < right, compare the bits at the mirrored positions:

• If s[left] == s[right], no flips are needed for this pair because the corresponding positions already match the reverse requirement.
• If s[left] != s[right], both positions are incorrect relative to the reversed string, so add 2 to flips.

5. Move the pointers inward:

• Increment left by 1
• Decrement right by 1

6. Continue until the pointers cross. If the binary string length is odd, the middle character is automatically correct because it maps to itself in the reverse.
7. Return the final value of flips.

Why it works

The key invariant is that each pair (left, right) corresponds exactly to how the reverse operation rearranges characters. Position left in the original string must equal position right in the reverse target. If the bits differ, both positions must be flipped to match the target arrangement. Since every pair is independent, summing the contribution from each mismatched pair guarantees the minimum number of flips.

Python Solution

class Solution:
    def minimumFlips(self, n: int) -> int:
        binary_string = bin(n)[2:]

        left = 0
        right = len(binary_string) - 1
        flips = 0

        while left < right:
            if binary_string[left] != binary_string[right]:
                flips += 2

            left += 1
            right -= 1

        return flips

The implementation begins by converting n into a binary string without the "0b" prefix. We then use two pointers to compare mirrored positions in the string.

The left pointer starts at the beginning, while right starts at the end. During each iteration, we check whether the two bits differ. If they do, we add 2 to the answer because both positions must be flipped to match the reversed target string.

After processing a pair, both pointers move inward. The loop stops once left >= right, meaning all mirrored pairs have been examined. Finally, the accumulated flip count is returned.

Go Solution

func minimumFlips(n int) int {
	binaryString := ""

	for n > 0 {
		if n%2 == 0 {
			binaryString = "0" + binaryString
		} else {
			binaryString = "1" + binaryString
		}
		n /= 2
	}

	left := 0
	right := len(binaryString) - 1
	flips := 0

	for left < right {
		if binaryString[left] != binaryString[right] {
			flips += 2
		}

		left++
		right--
	}

	return flips
}

The Go implementation follows the same two-pointer logic as the Python version. Since Go does not have a built-in bin() equivalent, we manually construct the binary representation by repeatedly extracting bits using modulo and division.

Strings in Go are byte-indexable, so comparing characters at mirrored positions is straightforward. Since the maximum input size is small, repeated string concatenation is acceptable here, though a strings.Builder could also be used for larger inputs.

Worked Examples

Example 1: n = 7

Binary representation:

s = "111"
reverse(s) = "111"

Step	Left	Right	s[left]	s[right]	Match?	Flips
1	0	2	1	1	Yes	0

The pointers cross after one comparison. Since all bits already match their reversed positions, the answer is 0.

Example 2: n = 10

Binary representation:

s = "1010"
reverse(s) = "0101"

Step	Left	Right	s[left]	s[right]	Match?	Flips
1	0	3	1	0	No	2
2	1	2	0	1	No	4

All mirrored pairs mismatch, so every bit must be flipped. The final answer is 4.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k)	We scan each bit at most once
Space	O(k)	Storing the binary representation requires k characters

Here, k represents the number of bits in the binary representation of n. Since n ≤ 10^9, k is at most around 30, making the algorithm effectively constant time in practice. The dominant memory cost comes from storing the binary string.

Test Cases

solution = Solution()

assert solution.minimumFlips(7) == 0      # Example: already equal to reverse
assert solution.minimumFlips(10) == 4     # Example: all bits differ

assert solution.minimumFlips(1) == 0      # Single-bit number
assert solution.minimumFlips(2) == 2      # "10" -> "01"
assert solution.minimumFlips(3) == 0      # "11" already symmetric
assert solution.minimumFlips(5) == 0      # "101" is unchanged after reverse
assert solution.minimumFlips(6) == 2      # "110" vs "011"

assert solution.minimumFlips(8) == 2      # "1000" vs "0001"
assert solution.minimumFlips(9) == 0      # "1001" palindrome
assert solution.minimumFlips(15) == 0     # "1111" already matches reverse

assert solution.minimumFlips(42) == 4     # "101010" vs "010101"
assert solution.minimumFlips(1000000000) >= 0  # Large constraint boundary

Test	Why
n = 7	Verifies provided example with zero flips
n = 10	Verifies provided example with maximum mismatch
n = 1	Smallest valid input
n = 2	Small even-length binary string
n = 3	Two identical bits
n = 5	Odd-length symmetric binary string
n = 6	Odd mismatch pattern
n = 8	Leading mismatch with zeros inside
n = 9	Binary palindrome
n = 15	All ones
n = 42	Alternating bit pattern
n = 1000000000	Large input boundary

Edge Cases

Single-bit numbers

When n = 1, the binary representation is "1". Since reversing a single-character string produces the same string, no flips are required. A naive implementation might accidentally mishandle this if it assumes at least one pair exists. Our implementation works correctly because the loop condition left < right immediately fails.

Odd-length binary strings

For odd-length strings such as "101" or "11111", the middle character maps to itself in the reversed string. Since a character always equals itself, the center never requires a flip. The implementation naturally handles this because the loop stops before the pointers meet.

Completely mismatched pairs

Strings like "1010" versus "0101" contain mirrored pairs where every bit differs. A common mistake is counting only one flip per mismatch pair. However, both positions must change to match the reversed target string, so each mismatch contributes 2 flips. Our implementation correctly increments the answer by 2 whenever a mirrored pair differs.