1. Minimum Operations to Make Binary Palindrome (LeetCode)
Model answer
The task
For each number in an array, find the fewest +1 or -1 operations needed to reach a number whose binary representation reads the same in both directions. Return the answer for every array element.
Key idea
Because each operation changes the value by one, the answer is the distance to the nearest binary-palindrome value. Generate the possible binary palindromes once, sort them, then use binary search to check the nearest candidate on either side of each number.
Approach
- Find the largest bit length among the input numbers.
- For each bit length, enumerate prefixes with a leading
1and mirror each prefix to form a palindrome of that length. - Include
0, then sort and deduplicate the candidates. - For each number, binary-search its insertion point among the candidates.
- Take the smaller distance to the candidate at that point or the one immediately before it.
from bisect import bisect_left
from typing import List
class Solution:
def minOperations(self, nums: List[int]) -> List[int]:
# Generate every binary palindrome up to one bit longer than
# the largest input, so the candidate set covers nearby values.
max_length = max((num.bit_length() for num in nums), default=0) + 1
palindromes = {0}
for length in range(1, max_length + 1):
half_length = (length + 1) // 2
first_prefix = 1 << (half_length - 1)
end_prefix = 1 << half_length
for prefix in range(first_prefix, end_prefix):
left = bin(prefix)[2:]
# For odd lengths, the middle bit must not be mirrored twice.
mirrored_part = left[:-1] if length % 2 else left
bits = left + mirrored_part[::-1]
palindromes.add(int(bits, 2))
ordered = sorted(palindromes)
answers = []
for num in nums:
index = bisect_left(ordered, num)
best = float("inf")
if index < len(ordered):
best = ordered[index] - num
if index > 0:
best = min(best, num - ordered[index - 1])
answers.append(best)
return answers
Complexity:
- Time: O(P log P + n log P), where
Pis the number of generated palindromes andnis the array length. - Space: O(P), for storing the palindrome candidates.
Common follow-ups
- Can the candidate set be reduced? Generate only palindromes near each number’s bit length, though this requires careful boundary handling.
- What if operations have different costs in each direction? Compare the upward and downward candidate distances using their respective costs.
- What if many queries arrive over time? Precompute and retain the sorted candidates, then answer each query with binary search.