Palindromic Number - Teradata Online Assessment

Problem Preview

"A positive integer is called **binary palindromic** if its binary representation (without leading zeros) reads the same from left to right and right to left. You are given an integer `N`. In a single operation, you may perform **one** of the following: * Increase the value of `N` by `1`. * Decrease the value of `N` by `1`. Determine the **minimum number of operations** required to transform `N` into a binary palindromic number. > **Note:** The binary representation of a number should always be considered without leading zeros. --- ## Input Format A single integer `N`. --- ## Output Format Print a single integer — the minimum number of operations needed to convert `N` into a binary palindromic number. --- ## Constraints * `1 ≤ N ≤ 10^9` --- ## Sample Input 1 ```text id="in1" 2 ``` ## Sample Output 1 ```text id="out1" 1 ``` ### Explanation The binary representation of `2` is `10`, which is not a palindrome. After increasing it by `1`, we obtain `3`, whose binary representation is `11`, a palindrome. Hence, the answer is `1`. --- ## Sample Input 2 ```text id="in2" 3 ``` ## Sample Output 2 ```text id="out2" 0 ``` ### Explanation The binary representation of `3` is `11`, which is already a palindrome. --- ## Sample Input 3 ```text id="in3" 10 ``` ## Sample Output 3 ```text id="out3" 1 ``` ### Explanation The binary representation of `10` is `1010`. Decreasing it by `1` gives `9`, whose binary representation is `1001`, a palindrome. Therefore, only one operation is required. --- ### Expected Approach Search outward from `N` by checking numbers at increasing distances until a binary palindrome is found. To verify whether a number is binary palindromic: 1. Convert it to binary without leading zeros. 2. Check if the binary string is equal to its reverse. **Time Complexity:** `O(k × log N)`, where `k` is the minimum distance to the nearest binary palindromic number. **Space Complexity:** `O(log N)`"