Minimum Operations to Make Binary Palindrome - Video Solutions
Leetcode Biweekly Contest 171 | Q1, Q2, Q3, Q4 Easy Solution Explained C++ | Fenwik Tree | Watch 2X🚀
Minimum Operations to Make Binary Palindrome - Video Solution
Watch 9 video solutions for Minimum Operations to Make Binary Palindrome, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by Rajan Keshari ( CSE - IIT Dhanbad ) has 663 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 50001 <= 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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers Pair Analysis | O(n) | O(1) | When operations directly fix mismatched symmetric pairs |
| Preprocessing + Binary Search | O(n log n) | O(n) | When you must check feasibility for a limited number of operations or range effects |