Welcome to Subscribe On Youtube

3766. Minimum Operations to Make Binary Palindrome

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

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.

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


  • 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


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

All Problems

All Solutions