Skip to main content
Talentd

Minimum Operations to Make Binary Palindrome - Solution & Explanation

MediumArrayTwo PointersBinary SearchBit Manipulation8 min readAsked at: Teradata
Practice this problem

Problem Statement

You are given an integer array nums.

For each element nums[i], you may perform the following operations any number of times (including zero):

  • Increase nums[i] by 1, or
  • Decrease nums[i] by 1.

A number is called a binary palindrome if its binary representation without leading zeros reads the same forward and backward.

Your task is to return an integer array ans, where ans[i] represents the minimum number of operations required to convert nums[i] into a binary palindrome.

 

Example 1:

Input: nums = [1,2,4]

Output: [0,1,1]

Explanation:

One optimal set of operations:

nums[i] Binary(nums[i]) Nearest
Palindrome		 Binary
(Palindrome)		 Operations Required ans[i]
1 1 1 1 Already palindrome 0
2 10 3 11 Increase by 1 1
4 100 3 11 Decrease by 1 1

Thus, ans = [0, 1, 1].

Example 2:

Input: nums = [6,7,12]

Output: [1,0,3]

Explanation:

One optimal set of operations:

nums[i] Binary(nums[i]) Nearest
Palindrome		 Binary
(Palindrome)		 Operations Required ans[i]
6 110 5 101 Decrease by 1 1
7 111 7 111 Already palindrome 0
12 1100 15 1111 Increase by 3 3

Thus, ans = [1, 0, 3].

 

Constraints:

  • 1 <= nums.length <= 5000
  • ​​​​​​​1 <= nums[i] <= 5000

Approach Overview

Problem Overview: You are given a binary array and need the minimum number of operations required to transform it into a palindrome. A palindrome reads the same from both ends, so elements at index i and n-1-i must match. The challenge is determining the smallest number of operations needed while efficiently handling mismatched pairs.

Approach 1: Two Pointers Pair Analysis (O(n) time, O(1) space)

Use the classic two pointers pattern. Start one pointer at the beginning and another at the end. For every pair (i, n-1-i), check if the bits differ. Each mismatch represents a required correction because a palindrome requires symmetric values. Iterate toward the center and count mismatches. This approach works well when each operation can directly fix a mismatched pair and is often the fastest baseline solution.

Approach 2: Preprocessing + Binary Search (O(n log n) time, O(n) space)

When operations affect ranges or require validation under constraints, combine preprocessing with binary search. First preprocess mismatched symmetric pairs and store them in a prefix structure so you can quickly determine how many conflicts exist in any region. Then binary search on the number of operations k. For each candidate k, run a feasibility check that uses the precomputed mismatch data to determine whether those operations can resolve all symmetric conflicts.

The preprocessing step compresses the mismatch information so validation becomes a quick scan rather than recomputing comparisons each time. During the check phase, you effectively simulate whether k operations can eliminate every pair conflict. The combination of prefix preprocessing and binary search dramatically reduces repeated work.

Because the array contains only binary values, operations and comparisons can also leverage bit manipulation tricks such as XOR to quickly detect mismatches (a ^ b == 1 means the pair differs). This keeps pair validation constant time.

Recommended for interviews: Start with the two‑pointer mismatch counting approach to demonstrate understanding of palindrome symmetry. Then discuss the preprocessing + binary search strategy for scenarios where operations affect ranges or require feasibility checks. Interviewers typically expect you to recognize the symmetric pair structure first, then optimize validation with prefix preprocessing.

Solution

We observe that the range of numbers given in the problem is only [1, 5000]. Therefore, we directly preprocess all binary palindromic numbers in the range [0, 2^{14}) and store them in an array, denoted as p.

Next, for each number x, we use binary search to find the first palindromic number greater than or equal to x in the array p, denoted as p[i], as well as the first palindromic number less than x, denoted as p[i - 1]. Then, we calculate the number of operations required to convert x to these two palindromic numbers and take the minimum value as the answer.

The time complexity is O(n times log M), and the space complexity is O(M). Where n is the length of the array nums, and M is the number of preprocessed binary palindromic numbers.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pointers Pair AnalysisO(n)O(1)When operations directly fix mismatched symmetric pairs
Preprocessing + Binary SearchO(n log n)O(n)When you must check feasibility for a limited number of operations or range effects

Video Solution

Leetcode Biweekly Contest 171 | Q1, Q2, Q3, Q4 Easy Solution Explained C++ | Fenwik Tree | Watch 2X🚀 • Rajan Keshari ( CSE - IIT Dhanbad ) • 663 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make Binary Palindrome easy or hard?
This problem is typically considered Medium difficulty. The core palindrome observation using two pointers is straightforward, but integrating preprocessing and binary search for operation feasibility requires stronger algorithmic reasoning.
Minimum Operations to Make Binary Palindrome Python/Java solution
Most implementations preprocess mismatched pairs and then apply binary search to determine the smallest valid number of operations. The logic translates easily across Python, Java, C++, Go, and TypeScript because it relies mainly on array traversal and simple arithmetic checks.
How to solve Minimum Operations to Make Binary Palindrome in O(n)?
An O(n) solution exists when each operation directly resolves mismatched symmetric pairs. Use two pointers starting from both ends of the array and compare values at positions i and n−1−i. Count the number of mismatches while moving toward the center.
What is the best approach for Minimum Operations to Make Binary Palindrome?
The most practical approach uses preprocessing with binary search. First record mismatched symmetric pairs in the binary array. Then binary search the minimum number of operations and validate feasibility using the preprocessed mismatch data. This keeps each check efficient and avoids recomputing comparisons.
Is Minimum Operations to Make Binary Palindrome asked at Google/Amazon/Meta?
Palindrome transformation and symmetric pair problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often combine two pointers, prefix preprocessing, or binary search feasibility checks.
What data structure is used in Minimum Operations to Make Binary Palindrome?
The solution primarily uses arrays and prefix preprocessing structures. Two pointers handle symmetric comparisons, while binary search determines the minimal operations. Bit manipulation like XOR can quickly detect mismatched binary pairs.
What is the time complexity of Minimum Operations to Make Binary Palindrome?
The optimal scalable approach runs in O(n log n) time with O(n) space. The preprocessing step scans the array once, and binary search performs log n feasibility checks. Each check uses prefix or mismatch information to validate in linear time or better.

Ready to solve this problem?

Practice Minimum Operations to Make Binary Palindrome with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays