3766. Minimum Operations to Make Binary Palindrome

SourceBiweekly Contest 171 Q2DifficultyMediumRating1656

Description

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 <= 5000
1 <= nums[i] <=5000

Solutions

Solution 1: Preprocessing + Binary Search

Thinking

\(nums[i]\le 5000\), so the nearest binary palindrome stays in a modest range. We precompute every binary palindrome below \(2^{14}\) and, for each \(x\), binary-search the two neighbors and take the smaller absolute difference.

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 \(\textit{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 \(\textit{p}\), denoted as \(\textit{p}[i]\), as well as the first palindromic number less than \(x\), denoted as \(\textit{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 \(\textit{nums}\), and \(M\) is the number of preprocessed binary palindromic numbers.

Python3JavaC++GoTypeScript

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 ans

class 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;
    }
};

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
}

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;
}

3766. Minimum Operations to Make Binary Palindrome

Description

Solutions

Solution 1: Preprocessing + Binary Search

Comments