3750. Minimum Number of Flips to Reverse Binary String

EasyBit ManipulationMathTwo PointersString

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a positive integer n.

Let s be the binary representation of n without leading zeros. For example, if n = 10, then s = "1010".

The reverse of a binary string s is obtained by writing the characters of s in the opposite order. For instance, the reverse of "1010" is "0101".

You may flip any bit in s, which means you can change a 0 to a 1, or change a 1 to a 0. Each flip affects exactly one bit.

Your task is to return the minimum number of flips required to make s equal to the reverse of its original form.

In other words, you want to transform the original string s into a palindrome, because a string equals its own reverse only when it is a palindrome. The goal is to find the least number of single-bit changes needed to achieve this.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Two pointers?

This problem maps to Two pointers through a short path in the full flowchart.

Comparing mirrored bit pairs from both ends with two pointers is identical to checking whether a string is a palindrome.

Open in Flowchart

Intuition

The key observation is that a string s is equal to its own reverse only when it is a palindrome. So our real goal is to turn s into a palindrome using the fewest flips.

In a palindrome, the character at position i (counting from the left) must match the character at the mirror position m - i - 1 (counting from the right), where m is the length of the string. So we only need to compare pairs of characters: the first with the last, the second with the second-to-last, and so on, working towards the center.

Now consider a single pair of mirrored characters s[i] and s[m - i - 1]:

If they are already the same, no flip is needed for this pair.
If they are different, we need to make them equal.

Here comes the subtle part. We are not building a palindrome and comparing it to the reverse separately; we want s itself to equal the reverse of the original s. When s[i] and s[m - i - 1] differ, simply flipping one of them is not enough, because flipping a bit also changes what the reverse looks like at the mirrored spot. To make a mismatched pair consistent in both s and its reverse, we must flip both positions in the pair. That is why each differing pair contributes 2 flips instead of 1.

So the strategy becomes simple:

Count the number of mirrored pairs that differ, call it cnt.
The answer is cnt * 2, since every mismatched pair costs exactly 2 flips.

This naturally leads to a two-pointer style scan from both ends of the string toward the middle.

Pattern Learn more about Math and Two Pointers patterns.

Solution Approach

Solution 1: Simulation

The implementation follows directly from the intuition and uses a straightforward simulation with a two-pointer idea.

Step 1: Convert the integer to a binary string.

We use bin(n) to get the binary representation of n. In Python, bin(n) returns a string with a "0b" prefix, so we slice off the first two characters with bin(n)[2:] to obtain the clean binary string s. We also record its length as m = len(s).

s = bin(n)[2:]
m = len(s)

Step 2: Compare mirrored pairs from both ends.

We only need to examine the first half of the string, because each position i in the first half has a unique mirror partner at position m - i - 1 in the second half. We let i run over range(m // 2), which covers exactly the left half:

When m is even, the two halves split cleanly.
When m is odd, the middle character maps to itself and is always equal to its mirror, so it never needs a flip and is safely skipped.

For each i, the expression s[i] != s[m - i - 1] evaluates to True (counted as 1) when the pair differs, and False (counted as 0) when the pair matches.

sum(s[i] != s[m - i - 1] for i in range(m // 2))

Step 3: Multiply by 2 to get the answer.

This sum gives us cnt, the number of mismatched pairs. Since each mismatched pair requires flipping both of its bits to keep s equal to the reverse of the original, the total number of flips is cnt * 2.

return sum(s[i] != s[m - i - 1] for i in range(m // 2)) * 2

Complexity Analysis:

Time complexity: O(log n). The binary string s has about log n characters, and we scan through half of them once.
Space complexity: O(log n), which is the space used to store the binary string s.

This approach avoids any extra data structures and solves the problem in a single linear pass over half the string, making it both simple and efficient.

Example Walkthrough

Let's trace through the solution with a small example: n = 10.

Step 1: Convert the integer to a binary string.

We compute bin(10), which gives "0b1010". Slicing off the "0b" prefix yields:

s = "1010"
m = len(s) = 4

So our string is s = "1010", with positions indexed 0, 1, 2, 3:

index:  0   1   2   3
char:  '1' '0' '1' '0'

Step 2: Compare mirrored pairs from both ends.

Since m = 4, we examine the first half by letting i run over range(m // 2) = range(2), so i = 0 and i = 1. For each i, we compare s[i] with its mirror partner s[m - i - 1].

Pair at i = 0: compare s[0] with s[4 - 0 - 1] = s[3].

s[0] = '1', s[3] = '0' → they differ → contributes 1.

'1' 0 1 '0'
 ↑       ↑
 mismatch

Pair at i = 1: compare s[1] with s[4 - 1 - 1] = s[2].

s[1] = '0', s[2] = '1' → they differ → contributes 1.

1 '0' '1' 0
   ↑   ↑
 mismatch

Adding these up, the number of mismatched pairs is:

cnt = 1 + 1 = 2

Step 3: Multiply by 2 to get the answer.

Each mismatched pair needs both of its bits flipped so that s stays equal to the reverse of the original. Therefore:

answer = cnt * 2 = 2 * 2 = 4

Verification:

The original string is "1010" and its reverse is "0101". To make s equal to its reverse, every one of the four characters must change:

s        = 1 0 1 0
reverse  = 0 1 0 1
            ✗ ✗ ✗ ✗   (all four positions differ)

All 4 bits must be flipped, which matches our computed result of 4. This confirms the approach: two mismatched pairs, each costing 2 flips, gives the minimum of 4.

Solution Implementation

1class Solution:
2    def minimumFlips(self, n: int) -> int:
3        # Convert n to its binary string representation (strip the '0b' prefix)
4        binary_str = bin(n)[2:]
5        length = len(binary_str)
6
7        # Count mismatched pairs by comparing each bit with its mirror position.
8        # For a palindrome check, position i should match position (length - i - 1).
9        mismatched_pairs = sum(
10            binary_str[i] != binary_str[length - i - 1]
11            for i in range(length // 2)
12        )
13
14        # Each mismatched pair contributes 2 (both bits in the pair are counted).
15        return mismatched_pairs * 2
16```
17
18**Notes on the changes made:**
19
201. **Naming standardization**: Renamed `s` → `binary_str`, `m` → `length`, and extracted the sum into `mismatched_pairs` for clarity. The method name `minimumFlips` was kept unchanged as requested.
21
222. **Python3 syntax**: The original code is already valid Python3. I kept the generator expression inside `sum()`, which is idiomatic and memory-efficient.
23
243. **Comments**: Added explanations for the binary conversion, the palindrome mirror-pair comparison, and the meaning of the `* 2` multiplier.
25
26**Alternative perspective** — if you prefer using bit operations instead of string conversion (avoiding the string allocation):
27
28```python3
29class Solution:
30    def minimumFlips(self, n: int) -> int:
31        # Get the number of bits in n (equivalent to len(bin(n)[2:]))
32        length = n.bit_length()
33
34        mismatched_pairs = 0
35        left = length - 1   # index of the most significant bit
36        right = 0           # index of the least significant bit
37
38        # Compare symmetric bit positions moving toward the center
39        while left > right:
40            # Extract the bit at each position and compare
41            if ((n >> left) & 1) != ((n >> right) & 1):
42                mismatched_pairs += 1
43            left -= 1
44            right += 1
45
46        return mismatched_pairs * 2
47

1class Solution {
2    public int minimumFlips(int n) {
3        // Convert the integer into its binary string representation
4        String binary = Integer.toBinaryString(n);
5        int length = binary.length();
6
7        // Count the number of mismatched symmetric pairs from both ends
8        int mismatchCount = 0;
9        for (int left = 0; left < length / 2; left++) {
10            int right = length - left - 1;
11            // If the characters at symmetric positions differ, it's a mismatch
12            if (binary.charAt(left) != binary.charAt(right)) {
13                mismatchCount++;
14            }
15        }
16
17        // Each mismatched pair requires flipping both bits, hence multiply by 2
18        return mismatchCount * 2;
19    }
20}
21

1class Solution {
2public:
3    int minimumFlips(int n) {
4        // Extract the binary digits of n into a vector,
5        // stored from least significant bit to most significant bit.
6        vector<int> bits;
7        while (n > 0) {
8            bits.push_back(n & 1);  // Store the lowest bit
9            n >>= 1;                // Shift right to process the next bit
10        }
11
12        int length = bits.size();
13        int flipCount = 0;
14
15        // Compare symmetric pairs of bits from both ends moving inward.
16        // For each mismatched pair, we need to flip in order to make
17        // the binary representation a palindrome.
18        for (int i = 0; i < length / 2; i++) {
19            if (bits[i] != bits[length - i - 1]) {
20                flipCount++;
21            }
22        }
23
24        // Each mismatched pair requires 2 flips (one on each side),
25        // so multiply the count by 2.
26        return flipCount * 2;
27    }
28};
29

1/**
2 * Calculates the minimum number of bit flips required to make the
3 * binary representation of n a palindrome.
4 *
5 * For each mismatched pair of bits (symmetric positions), two flips
6 * are needed to bring them into agreement.
7 *
8 * @param n - The input number whose binary form is examined.
9 * @returns The minimum number of flips, always an even count.
10 */
11function minimumFlips(n: number): number {
12    // Binary string representation of n (without the "0b" prefix).
13    const binaryStr: string = n.toString(2);
14    const length: number = binaryStr.length;
15
16    // Number of mismatched symmetric bit pairs.
17    let mismatchCount: number = 0;
18
19    // Compare bits from both ends toward the center.
20    for (let i = 0; i < length / 2; i++) {
21        // If the symmetric pair of bits differs, record a mismatch.
22        if (binaryStr[i] !== binaryStr[length - i - 1]) {
23            mismatchCount++;
24        }
25    }
26
27    // Each mismatched pair requires two flips to align.
28    return mismatchCount * 2;
29}
30

Time and Space Complexity

Time Complexity: O(log n)

The code first converts the integer n into its binary string representation via bin(n)[2:], which takes O(log n) time since the number of bits in n is proportional to log n. Let m = len(s) be the number of bits, where m = O(log n). The subsequent loop range(m // 2) iterates roughly m / 2 times, and each iteration performs a constant-time comparison s[i] != s[m - i - 1]. Thus the loop runs in O(m) = O(log n) time. The overall time complexity is therefore O(log n).
Space Complexity: O(log n)

The binary string s stores all the bits of n, requiring O(m) = O(log n) space. The generator expression passed to sum is evaluated lazily and uses only constant additional space, so it does not increase the asymptotic space usage. The dominant factor is the binary string storage, giving an overall space complexity of O(log n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Counting mismatches once instead of twice

The most common mistake is returning mismatched_pairs directly instead of mismatched_pairs * 2. It is tempting to reason "one mismatched pair only needs one flip" — flip a single bit so the pair matches. While that logic is correct for turning the string into a palindrome, it is wrong for this specific problem.

This problem requires the modified string to equal the reverse of the original string s, not just any palindrome. The reverse is a fixed target derived from the original bits. For a mismatched pair (s[i], s[m-i-1]), you must make s[i] equal to the original s[m-i-1] and make s[m-i-1] equal to the original s[i]. Since the pair differs, both positions are wrong relative to their target, so both must be flipped.

# WRONG: treats it as "make any palindrome"
return mismatched_pairs

# CORRECT: each mismatched pair needs both bits flipped
return mismatched_pairs * 2

Quick check with n = 10 (s = "1010"):

Reverse target is "0101".
Pair (s[0], s[3]) = ('1', '0') → mismatch → flip both.
Pair (s[1], s[2]) = ('0', '1') → mismatch → flip both.
Result: 2 * 2 = 4 flips. Returning just 2 would be incorrect.

Pitfall 2: Iterating over the whole string instead of half

If you loop over range(length) rather than range(length // 2), every mismatched pair gets counted twice (once from each end). Combined with the * 2 multiplier, this inflates the answer by a factor of 2. Always restrict the scan to the left half:

# WRONG: double-counts each pair
for i in range(length):
    ...

# CORRECT: scan only the first half
for i in range(length // 2):
    ...

Pitfall 3: Mishandling the middle bit on odd-length strings

When length is odd, the central character maps to itself and can never be a mismatch. Using range(length // 2) automatically and safely skips it. A subtle bug arises if you write range(length // 2 + 1) thinking you need to "include the middle" — this incorrectly compares s[length//2] with itself (harmless, always equal) only if your mirror index is exact, but any off-by-one in the mirror computation here can lead to comparing the wrong positions. Stick with length // 2 and the mirror index length - i - 1.

Pitfall 4: Forgetting that `bin(n)` includes the `"0b"` prefix

bin(10) returns "0b1010", not "1010". Failing to slice with [2:] means the prefix characters '0' and 'b' become part of the "binary string," corrupting both the length and the mirror comparisons.

# WRONG
binary_str = bin(n)        # "0b1010"

# CORRECT
binary_str = bin(n)[2:]    # "1010"

The bit-manipulation alternative sidesteps this entirely by using n.bit_length() and direct shifts, which is a reliable way to avoid prefix-related bugs.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering