3766. Minimum Operations to Make Binary Palindrome

MediumBit ManipulationArrayTwo PointersBinary Search

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

For each element nums[i], you may perform either of 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 (written without leading zeros) reads the same forward and backward. For example, 5 in binary is 101, which is a palindrome, while 6 in binary is 110, which is not.

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.

In other words, for each nums[i], you need to find the binary palindrome that is closest to nums[i] in value, and the answer is the absolute difference between nums[i] and that palindrome. Since each operation changes the value by exactly 1, the minimum number of operations equals the smallest distance from nums[i] to any binary palindrome.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

Precomputing all binary palindromes in sorted order and binary searching for the nearest one makes each query O(log n).

Open in Flowchart

Intuition

The key observation is that each operation changes a number by exactly 1, so the minimum number of operations to turn nums[i] into a binary palindrome is simply the absolute difference between nums[i] and the nearest binary palindrome.

This reduces the problem to: for each nums[i], find the binary palindrome closest to it in value.

Since the values in the problem are small (within a limited range), we can afford to precompute every binary palindrome up to a sufficiently large bound, for example all palindromes in [0, 2^14). Because we generate these palindromes by iterating numbers in increasing order, the resulting list p is automatically sorted.

Once we have a sorted list of all binary palindromes, finding the closest one to a given x becomes a classic binary search task. We locate the position where x would fit in the sorted list:

The palindrome at that position is the smallest palindrome greater than or equal to x, giving distance p[i] - x.
The palindrome just before it is the largest palindrome less than x, giving distance x - p[i - 1].

The closest palindrome must be one of these two neighbors, so we take the minimum of these two distances as the answer for x. Repeating this for every element in nums produces the full answer array.

Pattern Learn more about Two Pointers and Binary Search patterns.

Solution Approach

Solution 1: Preprocessing + Binary Search

We observe that the range of numbers given in the problem is small. Therefore, we directly preprocess all binary palindromic numbers in the range [0, 2^14) and store them in a sorted array, denoted as p.

Preprocessing step:

We iterate i over every integer in [0, 2^14). For each i, we convert it to its binary string using bin(i)[2:] (which strips the 0b prefix and naturally has no leading zeros). If the string equals its reverse s[::-1], then i is a binary palindrome, and we append it to p. Since we iterate in increasing order, p is automatically sorted in ascending order.

Query step:

For each number x in nums, we use binary search via bisect_left(p, x) to find the index i of the first palindrome in p that is greater than or equal to x. We then consider its two neighboring candidates:

If i < len(p), then p[i] is the smallest palindrome >= x, contributing a cost of p[i] - x.
If i >= 1, then p[i - 1] is the largest palindrome < x, contributing a cost of x - p[i - 1].

We take the minimum of these two costs as the answer for x, since the nearest binary palindrome must be one of these two neighbors. We initialize times to inf to safely handle boundary cases, then update it with the valid candidates.

Finally, we collect the answer for each element into the array ans and return it.

Complexity analysis:

Let M = 2^14 be the preprocessing bound and n be the length of nums. Building p takes O(M * log M) time (the log M factor comes from converting each number to a binary string of length up to log M).
Each query performs a binary search over p, which has O(log M) palindromes, so each query costs O(log(log M)), and all queries together cost O(n * log(log M)).
The space complexity is O(log M) for storing the list of palindromes (since the count of palindromes is far smaller than M).

Example Walkthrough

Let's trace through the solution with a small input: nums = [6, 9].

Step 1: Preprocessing — Build the sorted list of binary palindromes

We iterate over integers and keep only those whose binary representation reads the same forwards and backwards. Let's look at the first several integers:

`i`	`bin(i)[2:]`	Reversed	Palindrome?
0	`0`	`0`	✅ yes
1	`1`	`1`	✅ yes
2	`10`	`01`	❌ no
3	`11`	`11`	✅ yes
4	`100`	`001`	❌ no
5	`101`	`101`	✅ yes
6	`110`	`011`	❌ no
7	`111`	`111`	✅ yes
8	`1000`	`0001`	❌ no
9	`1001`	`1001`	✅ yes

Because we scan integers in increasing order, the collected palindromes are already sorted:

p = [0, 1, 3, 5, 7, 9, ...]

Step 2: Query each element with binary search

Query x = 6:

bisect_left(p, 6) returns index i = 4, since p[4] = 7 is the first palindrome >= 6.
Right neighbor: p[4] = 7 → cost 7 - 6 = 1.
Left neighbor: p[3] = 5 → cost 6 - 5 = 1.
Minimum cost = min(1, 1) = 1.

So 6 (binary 110) needs 1 operation to reach either 5 (101) or 7 (111).

Query x = 9:

bisect_left(p, 9) returns index i = 5, since p[5] = 9 is the first palindrome >= 9.
Right neighbor: p[5] = 9 → cost 9 - 9 = 0.
Left neighbor: p[4] = 7 → cost 9 - 7 = 2.
Minimum cost = min(0, 2) = 0.

So 9 (binary 1001) is already a binary palindrome and needs 0 operations.

Result:

ans = [1, 0]

This confirms the approach: precompute all binary palindromes once into a sorted list, then for each query locate the two closest candidates via binary search and take the smaller distance.

Solution Implementation

1from bisect import bisect_left
2from math import inf
3from typing import List
4
5# Precompute all binary palindromes within the range [0, 2^14).
6# A binary palindrome is a number whose binary representation
7# (without the "0b" prefix) reads the same forwards and backwards.
8binary_palindromes = []
9for value in range(1 << 14):
10    binary_str = bin(value)[2:]
11    if binary_str == binary_str[::-1]:
12        binary_palindromes.append(value)
13
14
15class Solution:
16    def minOperations(self, nums: List[int]) -> List[int]:
17        ans = []
18        for num in nums:
19            # Find the insertion index for num in the sorted palindrome list.
20            idx = bisect_left(binary_palindromes, num)
21            min_ops = inf
22
23            # Compare with the nearest palindrome >= num (to the right).
24            if idx < len(binary_palindromes):
25                min_ops = min(min_ops, binary_palindromes[idx] - num)
26
27            # Compare with the nearest palindrome < num (to the left).
28            if idx >= 1:
29                min_ops = min(min_ops, num - binary_palindromes[idx - 1])
30
31            ans.append(min_ops)
32        return ans
33

1class Solution {
2    // Precomputed list of binary palindromes (numbers whose binary
3    // representation is the same when reversed), kept in ascending order.
4    private static final List<Integer> PALINDROMES = new ArrayList<>();
5
6    static {
7        // Upper bound: generate all binary palindromes below 2^14 (16384).
8        final int limit = 1 << 14;
9        for (int i = 0; i < limit; i++) {
10            String binary = Integer.toBinaryString(i);
11            String reversedBinary = new StringBuilder(binary).reverse().toString();
12            // If the binary string equals its reverse, it is a binary palindrome.
13            if (binary.equals(reversedBinary)) {
14                PALINDROMES.add(i);
15            }
16        }
17    }
18
19    public int[] minOperations(int[] nums) {
20        int n = nums.length;
21        int[] ans = new int[n];
22        // Initialize with the maximum value so any valid difference is smaller.
23        Arrays.fill(ans, Integer.MAX_VALUE);
24
25        for (int k = 0; k < n; ++k) {
26            int x = nums[k];
27            // Find the index of the first palindrome >= x (lower bound).
28            int idx = binarySearch(PALINDROMES, x);
29
30            // Candidate 1: the closest palindrome that is >= x.
31            if (idx < PALINDROMES.size()) {
32                ans[k] = Math.min(ans[k], PALINDROMES.get(idx) - x);
33            }
34            // Candidate 2: the closest palindrome that is < x.
35            if (idx >= 1) {
36                ans[k] = Math.min(ans[k], x - PALINDROMES.get(idx - 1));
37            }
38        }
39
40        return ans;
41    }
42
43    /**
44     * Standard lower-bound binary search.
45     * Returns the index of the first element in {@code palindromes}
46     * that is greater than or equal to {@code x}.
47     *
48     * @param palindromes a list sorted in ascending order
49     * @param x           the target value
50     * @return the lower-bound index for {@code x}
51     */
52    private int binarySearch(List<Integer> palindromes, int x) {
53        int left = 0, right = palindromes.size();
54        while (left < right) {
55            // Unsigned right shift avoids overflow when computing the midpoint.
56            int mid = (left + right) >>> 1;
57            if (palindromes.get(mid) >= x) {
58                right = mid;
59            } else {
60                left = mid + 1;
61            }
62        }
63        return left;
64    }
65}
66

1// Precomputed list of all binary palindromes within the search range.
2vector<int> binaryPalindromes;
3
4// Static initializer: runs once before main() to populate binaryPalindromes.
5auto init = [] {
6    const int kRange = 1 << 14;  // Upper bound: 16384 possible values.
7    for (int value = 0; value < kRange; ++value) {
8        // Convert value to a 14-bit binary string.
9        string bits = bitset<14>(value).to_string();
10
11        // Strip leading zeros to get the actual binary representation.
12        // If the string is all zeros, keep only the last character ("0").
13        size_t firstOne = bits.find_first_not_of('0');
14        bits = bits.substr(firstOne == string::npos ? 13 : firstOne);
15
16        // Build the reversed copy of the trimmed binary string.
17        string reversedBits = bits;
18        reverse(reversedBits.begin(), reversedBits.end());
19
20        // Keep the value only if its binary form is a palindrome.
21        if (bits == reversedBits) {
22            binaryPalindromes.push_back(value);
23        }
24    }
25    return 0;
26}();
27
28class Solution {
29public:
30    vector<int> minOperations(vector<int>& nums) {
31        int n = nums.size();
32        // ans[k] holds the minimum distance from nums[k] to a binary palindrome.
33        vector<int> ans(n, INT_MAX);
34
35        for (int k = 0; k < n; ++k) {
36            int x = nums[k];
37
38            // Find the first palindrome >= x using binary search.
39            int idx = lower_bound(binaryPalindromes.begin(),
40                                  binaryPalindromes.end(), x) -
41                      binaryPalindromes.begin();
42
43            // Candidate 1: the nearest palindrome that is >= x.
44            if (idx < static_cast<int>(binaryPalindromes.size())) {
45                ans[k] = min(ans[k], binaryPalindromes[idx] - x);
46            }
47
48            // Candidate 2: the nearest palindrome that is < x.
49            if (idx >= 1) {
50                ans[k] = min(ans[k], x - binaryPalindromes[idx - 1]);
51            }
52        }
53
54        return ans;
55    }
56};
57

1/**
2 * Precompute all "binary palindromes" within a 14-bit range.
3 * A binary palindrome is a number whose binary string reads the
4 * same forwards and backwards (e.g. 5 -> "101", 9 -> "1001").
5 * The resulting array is naturally sorted in ascending order
6 * because we iterate from small to large values.
7 */
8const binaryPalindromes: number[] = (() => {
9    const result: number[] = [];
10    const limit = 1 << 14; // Upper bound (2^14 = 16384) for candidate values
11    for (let value = 0; value < limit; value++) {
12        const binaryStr = value.toString(2);
13        const reversedStr = binaryStr.split('').reverse().join('');
14        if (binaryStr === reversedStr) {
15            result.push(value);
16        }
17    }
18    return result;
19})();
20
21/**
22 * Find the leftmost index at which `target` could be inserted into the
23 * sorted array `arr` while keeping it sorted (lower-bound binary search).
24 * This mirrors the behavior of lodash's `_.sortedIndex`.
25 *
26 * @param arr    - A sorted array of numbers (ascending).
27 * @param target - The value to locate the insertion point for.
28 * @returns The smallest index `i` such that `arr[i] >= target`.
29 */
30function sortedIndex(arr: number[], target: number): number {
31    let low = 0;
32    let high = arr.length;
33    while (low < high) {
34        const mid = (low + high) >> 1; // Midpoint without overflow concerns here
35        if (arr[mid] < target) {
36            low = mid + 1; // Discard the left half, target lies to the right
37        } else {
38            high = mid; // `mid` might be the answer, keep it in range
39        }
40    }
41    return low;
42}
43
44/**
45 * For each element in `nums`, compute the minimum number of operations
46 * (absolute difference) needed to turn it into the nearest binary palindrome.
47 *
48 * Strategy:
49 *   - Use binary search to find the insertion index `i` of the value.
50 *   - The candidate just at/above the value is `binaryPalindromes[i]`.
51 *   - The candidate just below the value is `binaryPalindromes[i - 1]`.
52 *   - The answer is the smaller distance to these two neighbors.
53 *
54 * @param nums - The input array of numbers.
55 * @returns An array where each entry is the minimal distance to a binary palindrome.
56 */
57function minOperations(nums: number[]): number[] {
58    const ans: number[] = Array(nums.length).fill(Number.MAX_SAFE_INTEGER);
59
60    for (let k = 0; k < nums.length; k++) {
61        const x = nums[k];
62        // Locate insertion point within the sorted palindrome list.
63        const i = sortedIndex(binaryPalindromes, x);
64
65        // Distance to the nearest palindrome that is >= x.
66        if (i < binaryPalindromes.length) {
67            ans[k] = binaryPalindromes[i] - x;
68        }
69
70        // Distance to the nearest palindrome that is < x; keep the minimum.
71        if (i >= 1) {
72            ans[k] = Math.min(ans[k], x - binaryPalindromes[i - 1]);
73        }
74    }
75
76    return ans;
77}
78

Time and Space Complexity

Time complexity: O(n × log M). The preprocessing loop runs 1 << 14 times, and for each value it reverses a binary string of length up to 14, which is a constant-bounded cost, so building the list p of binary palindromic numbers takes O(M × log M) where M is the number of palindromes collected (its length is bounded). In the main routine, for each of the n elements in nums, a bisect_left is performed over the list p, costing O(log M) per query. Therefore the query phase is O(n × log M), and this dominates with respect to n, giving an overall time complexity of O(n × log M).
Space complexity: O(M). The list p stores all preprocessed binary palindromic numbers, requiring O(M) space, where M is the number of such numbers. The answer array ans uses O(n) space for output, but the auxiliary space dominated by the palindrome table is O(M).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Hardcoding the preprocessing bound `2^14` without checking the actual constraints

The most dangerous mistake is assuming 2^14 (i.e., 16384) is large enough to cover all possible values in nums. If any nums[i] is close to or larger than the biggest palindrome below 16384, the binary search may not find a valid palindrome to the right, and the algorithm will only rely on the left neighbor — which is fine for boundaries, but if nums[i] itself exceeds the largest precomputed palindrome significantly, the left-only candidate gives a wildly incorrect (too large) answer because the true nearest palindrome was never generated.

Why it breaks: Suppose nums[i] = 20000 but you only precomputed palindromes up to 16384. The binary search returns idx = len(p), so the right candidate is skipped. The left candidate (the largest palindrome below 16384) yields a cost of roughly 20000 - 16383, even though a valid binary palindrome much closer to 20000 exists but was never generated.

Solution: Make the bound depend on the constraints. Choose a power of two strictly greater than the maximum possible nums[i]. A robust approach is to compute the bound from the input itself:

from bisect import bisect_left
from math import inf
from typing import List


class Solution:
    def minOperations(self, nums: List[int]) -> List[int]:
        # Derive a safe bound from the input so we never miss a near palindrome.
        max_num = max(nums) if nums else 0
        # The next binary palindrome is at most ~2x away; pad generously.
        limit = (max_num + 2) << 1

        palindromes = []
        for value in range(limit + 1):
            s = bin(value)[2:]
            if s == s[::-1]:
                palindromes.append(value)

        ans = []
        for num in nums:
            idx = bisect_left(palindromes, num)
            min_ops = inf
            if idx < len(palindromes):
                min_ops = min(min_ops, palindromes[idx] - num)
            if idx >= 1:
                min_ops = min(min_ops, num - palindromes[idx - 1])
            ans.append(min_ops)
        return ans

Pitfall 2: Forgetting that `0` and negative-distance reasoning around boundaries

When num is itself a binary palindrome, bisect_left returns the index of that palindrome (since p[idx] == num), so the right candidate correctly yields 0. A subtle bug arises if someone uses bisect_right instead of bisect_left here: bisect_right would skip past the exact match, making p[idx] > num and forcing the answer to come from neighbors, which could give a non-zero (incorrect) result for an already-palindromic number.

Solution: Always use bisect_left so an exact match is included as the right candidate, guaranteeing a cost of 0 when num is already a binary palindrome. The provided code does this correctly — just be careful not to "optimize" it into bisect_right.

Pitfall 3: Initializing `min_ops` to `0` instead of `inf`

If you initialize min_ops = 0, the min(...) calls can never update it upward, so every answer collapses to 0. The initialization must be inf so the first valid candidate properly sets the value. At least one of the two branches (idx < len(p) or idx >= 1) always executes for a non-empty palindrome list (which always contains 0 and 1), so inf is guaranteed to be replaced by a real value.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering