Minimum Operations to Make Binary Palindrome solution and explanation
7 more videos on this problem
Minimum Operations to Make Binary Palindrome | LeetCode 3766 | Biweekly Contest 171Sanyam IIT Guwahati · 10:51 · 546 views
Minimum Operations to Make Binary Palindrome 🔥 Leetcode 3766 | Biweekly Contest 171 Q2 | Optimal Study Placement · 19:47 · 168 views
3766. Minimum Operations to Make Binary Palindrome | Biweekly Contest 171 | LeetcodeRapid Syntax · 17:00 · 122 views
3766. Minimum Operations to Make Binary Palindrome (Leetcode Medium)Programming Live with Larry · 11:58 · 119 views
Leetcode 3766,3767|Minimum Operations to Make Binary Palindrome|Maximize Point After Choosing K TaskCodeWithMeGuys · 25:00 · 101 views
LeetCode 3766 – Minimum Operations to Make Binary Palindrome | Greedy + Two Pointer ExplainedProof2Code · 11:26 · 27 views
LeetCode Biweekly Contest 171 | LeetCode 3765 | LeetCode 3766 | LeetCode 3767codeTips · 20:43 · 26 views
Leetcode 3766 | Minimum Operations to Make Binary Palindrome | Step by stepDSA - Just Intuition · 42:23 · 2 views
The problem
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.
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.
p = []
for i in range(1 << 14):
s = bin(i)[2:]
if s == s[::-1]:
p.append(i)
class Solution:
def minOperations(self, nums: List[int]) -> List[int]:
ans = []
for x in nums:
i = bisect_left(p, x)
times = inf
if i < len(p):
times = min(times, p[i] - x)
if i >= 1:
times = min(times, x - p[i - 1])
ans.append(times)
return ansclass Solution {
private static final List<Integer> p = new ArrayList<>();
static {
int N = 1 << 14;
for (int i = 0; i < N; i++) {
String s = Integer.toBinaryString(i);
String rs = new StringBuilder(s).reverse().toString();
if (s.equals(rs)) {
p.add(i);
}
}
}
public int[] minOperations(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, Integer.MAX_VALUE);
for (int k = 0; k < n; ++k) {
int x = nums[k];
int i = binarySearch(p, x);
if (i < p.size()) {
ans[k] = Math.min(ans[k], p.get(i) - x);
}
if (i >= 1) {
ans[k] = Math.min(ans[k], x - p.get(i - 1));
}
}
return ans;
}
private int binarySearch(List<Integer> p, int x) {
int l = 0, r = p.size();
while (l < r) {
int mid = (l + r) >>> 1;
if (p.get(mid) >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}vector<int> p;
auto init = [] {
int N = 1 << 14;
for (int i = 0; i < N; ++i) {
string s = bitset<14>(i).to_string();
s = s.substr(s.find_first_not_of('0') == string::npos ? 13 : s.find_first_not_of('0'));
string rs = s;
reverse(rs.begin(), rs.end());
if (s == rs) {
p.push_back(i);
}
}
return 0;
}();
class Solution {
public:
vector<int> minOperations(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, INT_MAX);
for (int k = 0; k < n; ++k) {
int x = nums[k];
int i = lower_bound(p.begin(), p.end(), x) - p.begin();
if (i < (int) p.size()) {
ans[k] = min(ans[k], p[i] - x);
}
if (i >= 1) {
ans[k] = min(ans[k], x - p[i - 1]);
}
}
return ans;
}
};const p: number[] = (() => {
const res: number[] = [];
const N = 1 << 14;
for (let i = 0; i < N; i++) {
const s = i.toString(2);
if (s === s.split('').reverse().join('')) {
res.push(i);
}
}
return res;
})();
function minOperations(nums: number[]): number[] {
const ans: number[] = Array(nums.length).fill(Number.MAX_SAFE_INTEGER);
for (let k = 0; k < nums.length; k++) {
const x = nums[k];
const i = _.sortedIndex(p, x);
if (i < p.length) {
ans[k] = p[i] - x;
}
if (i >= 1) {
ans[k] = Math.min(ans[k], x - p[i - 1]);
}
}
return ans;
}var p []int
func init() {
N := 1 << 14
for i := 0; i < N; i++ {
s := strconv.FormatInt(int64(i), 2)
if isPalindrome(s) {
p = append(p, i)
}
}
}
func isPalindrome(s string) bool {
runes := []rune(s)
for i := 0; i < len(runes)/2; i++ {
if runes[i] != runes[len(runes)-1-i] {
return false
}
}
return true
}
func minOperations(nums []int) []int {
ans := make([]int, len(nums))
for k, x := range nums {
i := sort.SearchInts(p, x)
t := math.MaxInt32
if i < len(p) {
t = p[i] - x
}
if i >= 1 {
t = min(t, x-p[i-1])
}
ans[k] = t
}
return ans
}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 |
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.