Skip to main content
Talentd

Minimum Number of Flips to Reverse Binary String - Solution & Explanation

EasyMathTwo PointersStringBit Manipulation6 min read
Practice this problem

Problem Statement

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 <= 109

Approach Overview

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

Solution

We first convert the integer n into a binary string s. Then we use two pointers to traverse from both ends of the string towards the center, counting the number of positions where the characters differ, denoted as cnt. Since each flip can only affect one bit, the total number of flips is cnt times 2.

The time complexity is O(log n) and the space complexity is O(log n), where n is the input integer.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Reverse String + CompareO(n)O(n)Good for quick implementation when extra memory is acceptable
Two Pointers SimulationO(n)O(1)Preferred solution in interviews and production due to constant space

Video Solution

3750. Minimum Number of Flips to Reverse Binary String (Leetcode Easy) • Programming Live with Larry • 211 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Minimum Number of Flips to Reverse Binary String easy or hard?
Minimum Number of Flips to Reverse Binary String is considered an Easy problem. The key idea is recognizing that mirrored positions must match. Once that symmetry is identified, a simple two‑pointer scan produces the answer in linear time.
Minimum Number of Flips to Reverse Binary String Python/Java solution
Most implementations iterate with two indices from both ends of the string. If the characters differ, increment a counter and move both pointers inward. The same logic works in Python, Java, C++, Go, and TypeScript with O(n) time complexity.
How to solve Minimum Number of Flips to Reverse Binary String in O(n)?
Use two pointers. Initialize one pointer at the start and one at the end of the string. Move both toward the center while checking if the characters match. Whenever s[left] and s[right] differ, increment the flip counter. Each pair requires at most one flip, giving an O(n) time and O(1) space solution.
What is the best approach for Minimum Number of Flips to Reverse Binary String?
The two pointers approach is the most efficient. Start one pointer at the beginning of the string and another at the end, comparing mirrored characters. Every time the two characters differ, one flip is required to make them equal. This solution runs in O(n) time and O(1) extra space.
Is Minimum Number of Flips to Reverse Binary String asked at Google/Amazon/Meta?
Problems involving symmetric comparisons, binary strings, and two‑pointer techniques appear frequently in coding interviews at companies like Amazon, Google, and Meta. Variants of palindrome or mirrored string correction problems are common in interview question banks.
What data structure is used in Minimum Number of Flips to Reverse Binary String?
The problem mainly relies on string traversal with the two pointers technique. No advanced data structures are required. The algorithm simply compares characters at mirrored indices and counts mismatches.
What is the time complexity of Minimum Number of Flips to Reverse Binary String?
The optimal algorithm runs in O(n) time because the string is scanned once while comparing symmetric positions. Space complexity can be O(1) when using two pointers, or O(n) if you explicitly build the reversed string for comparison.

Ready to solve this problem?

Practice Minimum Number of Flips to Reverse Binary String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer