LeetCode 3766 - Minimum Operations to Make Binary Palindrome

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Bit Manipulation

Solution

Problem Understanding

This problem asks us to find the minimum number of increment or decrement operations needed to convert each number in a list into a binary palindrome. A binary palindrome is a number whose binary representation reads the same forwards and backwards once leading zeros are removed. For example, the number 5 in binary is 101, which is a palindrome, while 6 in binary is 110, which is not a palindrome.

The input is an array of integers nums, each ranging from 1 to 5000, and the output must be an array ans of the same length where ans[i] indicates the minimum operations to convert nums[i] to a binary palindrome. The operations allowed are simple increments or decrements of 1.

The constraints indicate that nums can contain up to 5000 elements and each number is at most 5000. This implies that a brute-force approach checking every number up to some high limit may be feasible if optimized properly, but iterating blindly over all possible numbers could be inefficient. Important edge cases include numbers that are already binary palindromes, numbers close to the boundaries of the allowed range, and numbers that require checking both upward and downward directions to find the nearest palindrome.

Approaches

The brute-force approach would consider each number and increment or decrement it one step at a time, checking at each step if it is a binary palindrome. This guarantees the correct answer because eventually we will reach the nearest palindrome, but it is inefficient, particularly for numbers that are far from their nearest palindrome. Checking the binary form for every candidate number would be costly.

The key insight for the optimal approach is that we can precompute all binary palindromes within the problem's number range (1 to 5000). Then, for each number in nums, we can find the closest binary palindrome using a binary search, because the list of palindromes can be sorted in ascending order. This reduces the problem from checking all numbers individually to a simple search in a precomputed list, dramatically improving performance.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * max_val * log(max_val))	O(1)	Check each number incrementally for palindrome by converting to binary
Optimal	O(n * log P)	O(P)	Precompute all palindromes up to maximum number (P≈5000), then binary search nearest

Algorithm Walkthrough

Precompute all binary palindromes in the range [1, max(nums)]. To do this efficiently, generate palindromes by constructing half the binary string and mirroring it.
Sort the precomputed palindromes. This ensures that binary search can be applied.
For each number num in nums, perform a binary search on the palindrome list to find the closest palindrome(s). Because the palindrome list is sorted, binary search ensures O(log P) search time.
Compute the difference between num and the nearest palindrome(s) to determine the minimum operations required.
Append this minimum number of operations to the result array.
Return the result array after processing all numbers.

Why it works: By precomputing all binary palindromes and using binary search, we guarantee that we find the closest palindrome efficiently. The minimum operation is simply the absolute difference to the nearest palindrome.

Python Solution

from typing import List
import bisect

class Solution:
    def minOperations(self, nums: List[int]) -> List[int]:
        def generate_palindromes(limit: int) -> List[int]:
            palindromes = set()
            for length in range(1, 13):  # max binary length for 5000 is 13
                half_len = (length + 1) // 2
                for i in range(1 << (half_len - 1), 1 << half_len):
                    bin_half = bin(i)[2:]
                    if length % 2 == 0:
                        pal = bin_half + bin_half[::-1]
                    else:
                        pal = bin_half + bin_half[-2::-1]
                    val = int(pal, 2)
                    if val <= limit:
                        palindromes.add(val)
            return sorted(palindromes)
        
        max_num = max(nums)
        palindromes = generate_palindromes(max_num)
        
        result = []
        for num in nums:
            idx = bisect.bisect_left(palindromes, num)
            ops = float('inf')
            if idx < len(palindromes):
                ops = min(ops, abs(palindromes[idx] - num))
            if idx > 0:
                ops = min(ops, abs(palindromes[idx - 1] - num))
            result.append(ops)
        return result

The Python implementation first generates all binary palindromes within the maximum number range using a mirror technique for half the binary string. It then uses the bisect module to efficiently find the closest palindrome for each number. The result array stores the minimum operation counts.

Go Solution

package main

import (
    "math"
    "sort"
)

func minOperations(nums []int) []int {
    generatePalindromes := func(limit int) []int {
        palindromes := []int{}
        for length := 1; length <= 13; length++ {
            halfLen := (length + 1) / 2
            start := 1 << (halfLen - 1)
            end := 1 << halfLen
            for i := start; i < end; i++ {
                binHalf := strconv.FormatInt(int64(i), 2)
                var pal string
                if length%2 == 0 {
                    pal = binHalf + reverseString(binHalf)
                } else {
                    pal = binHalf + reverseString(binHalf[:len(binHalf)-1])
                }
                val, _ := strconv.ParseInt(pal, 2, 64)
                if int(val) <= limit {
                    palindromes = append(palindromes, int(val))
                }
            }
        }
        sort.Ints(palindromes)
        return palindromes
    }
    
    reverseString := func(s string) string {
        runes := []rune(s)
        for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
            runes[i], runes[j] = runes[j], runes[i]
        }
        return string(runes)
    }

    maxNum := 0
    for _, num := range nums {
        if num > maxNum {
            maxNum = num
        }
    }
    palindromes := generatePalindromes(maxNum)

    result := make([]int, len(nums))
    for i, num := range nums {
        idx := sort.Search(len(palindromes), func(j int) bool { return palindromes[j] >= num })
        ops := math.MaxInt32
        if idx < len(palindromes) {
            ops = min(ops, abs(palindromes[idx]-num))
        }
        if idx > 0 {
            ops = min(ops, abs(palindromes[idx-1]-num))
        }
        result[i] = ops
    }
    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

The Go solution mirrors the Python logic. It constructs binary palindromes and uses sort.Search to efficiently locate the nearest palindrome for each number. Extra helper functions handle string reversal, absolute value, and minimum calculation.

Worked Examples

Example 1: nums = [1, 2, 4]

num	binary	closest palindrome	operations
1	1	1	0
2	10	3 (11)	1
4	100	3 (11)	1

Example 2: nums = [6, 7, 12]

num	binary	closest palindrome	operations
6	110	5 (101)	1
7	111	7 (111)	0
12	1100	15 (1111)	3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * log P)	Precompute all palindromes in O(P), then for each of n numbers, binary search in O(log P)
Space	O(P)	Store all precomputed palindromes, where P is the number of palindromes up to max(nums)

The time complexity is efficient because P is bounded by roughly 5000, and binary search reduces per-number computation to logarithmic time.

Test Cases

# Provided examples
assert Solution().minOperations([1,2,4]) == [0,1,1]  # basic small numbers
assert Solution().minOperations([6,7,12]) == [1,0,3]  # mixed increments/decrements

# Edge cases
assert Solution().minOperations([1]) == [0]  # smallest number