Watch 3 video solutions for Minimum Number of Flips to Reverse Binary String, a easy level problem involving Math, Two Pointers, String. This walkthrough by ADevOpsBeginner has 158 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a positive integer n.
Let s be the binary representation of n without leading zeros.
The reverse of a binary string s is obtained by writing the characters of s in the opposite order.
You may flip any bit in s (change 0 → 1 or 1 → 0). Each flip affects exactly one bit.
Return the minimum number of flips required to make s equal to the reverse of its original form.
Example 1:
Input: n = 7
Output: 0
Explanation:
The binary representation of 7 is "111". Its reverse is also "111", which is the same. Hence, no flips are needed.
Example 2:
Input: n = 10
Output: 4
Explanation:
The binary representation of 10 is "1010". Its reverse is "0101". All four bits must be flipped to make them equal. Thus, the minimum number of flips required is 4.
Constraints:
1 <= n <= 109Problem Overview: You are given a binary string. The goal is to determine the minimum number of bit flips required so the string becomes equal to its reverse. A flip changes a character from 0 to 1 or from 1 to 0. The task reduces to fixing mismatched mirrored positions in the string.
Approach 1: Reverse String + Compare (Simulation) (O(n) time, O(n) space)
Create the reversed version of the string and compare it with the original character by character. For every index i, check whether s[i] matches rev[i]. If the characters differ, a flip is required to make them equal. Count the number of mismatches and divide by two because each mismatch pair corresponds to a mirrored conflict between two positions. This approach is straightforward and mirrors how you would reason about the problem manually, but it allocates an extra string.
Approach 2: Two Pointers (Simulation) (O(n) time, O(1) space)
Instead of explicitly reversing the string, compare mirrored characters directly using the two pointers technique. Start one pointer at the beginning (left) and another at the end (right). Move both toward the center while checking whether s[left] equals s[right]. If they differ, one flip is enough to make the pair match, so increment the flip counter. Continue until the pointers meet. This works because each pair must contain identical bits for the string to match its reverse. The algorithm performs a single pass through the string and uses constant extra memory.
This method is essentially a direct simulation of the constraints imposed by the reversed string. Since each step compares symmetric indices, it naturally aligns with problems involving string processing and simple bit manipulation. The key insight is that every mirrored pair can be corrected with at most one flip.
Recommended for interviews: The two‑pointer approach is what interviewers typically expect. It shows you recognize the symmetry in the string and avoid unnecessary memory allocation. Mentioning the reverse‑and‑compare simulation first demonstrates baseline reasoning, while the two‑pointer solution shows you can optimize both space and implementation clarity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse String + Compare | O(n) | O(n) | Good for quick implementation when extra memory is acceptable |
| Two Pointers Simulation | O(n) | O(1) | Preferred solution in interviews and production due to constant space |