Given an integer n, you need to find the largest integer m (m < n) such that m XOR n is a palindrome. If there is no such integer, return -1.
Examples :
Input: n = 10
Output: 5
Explanation:
- The binary representation of 10 is 1010.
- The binary representation of 5 is 0101.
The XOR of 10 and 5 is 1111, which is a palindrome.
Input: n = 7
Output: 5
Explanation:
- The binary representation of 7 is 111.
- The binary representation of 3 is 101.
The XOR of 7 and 3 is 101, which is a palindrome.
Approach: This can be solved with the following idea:
This can be solved by mathematical and logical observations.
- Finding the number of bits in the input integer n using the formula numBits = log2(n) + 1.
- It then iterates from the maximum possible value of m down to 0.
- Inside the loop, the function computes the XOR of m and n and checks if it is a palindrome. To check if the XOR is a palindrome, it starts by comparing the first and last bits of the XOR and then moves toward the middle of the XOR, comparing the corresponding bits at each end.
- The loop stops as soon as the comparison reaches the middle of the XOR. If the XOR is a palindrome, the function returns m.
- If no integer m is found such that m XOR n is a palindrome, the function returns -1.
Below is the implementation of the code :
C++
// C++ code for the above approach:#include <bits/stdc++.h>#include <bitset>using namespace std;// Function to find largest Integer// forming palindrome with nint largestPalindromeXOR(int n){ // Find the number of bits in n int numBits = log2(n) + 1; // Iterate from the maximum possible // value of m down to 0 for (int m = n - 1; m >= 0; m--) { // Compute the XOR of m and n int x = m ^ n; // Check if the XOR of m and n // is a palindrome int i = 0, j = numBits - 1; bool isPalindrome = true; while (i < j) { if (x & (1 << i)) { if (!(x & (1 << j))) { isPalindrome = false; break; } } else { if (x & (1 << j)) { isPalindrome = false; break; } } i++; j--; } // If the XOR of m and n is a // palindrome, return m if (isPalindrome) { return m; } } // If no such integer is found, // return -1 return -1;}// Driver codeint main(){ int n = 10; // Function call int largestPalXOR = largestPalindromeXOR(n); if (largestPalXOR == -1) { cout << "No such integer exists" << endl; } else { cout << largestPalXOR << endl; } return 0;} |
Java
import java.util.*;public class LargestPalindromeXOR { // Function to find largest Integer forming palindrome // with n public static int largestPalindromeXOR(int n) { // Find the number of bits in n int numBits = (int)(Math.log(n) / Math.log(2)) + 1; // Iterate from the maximum possible value of m down // to 0 for (int m = n - 1; m >= 0; m--) { // Compute the XOR of m and n int x = m ^ n; // Check if the XOR of m and n is a palindrome int i = 0, j = numBits - 1; boolean isPalindrome = true; while (i < j) { if (((x & (1 << i)) != 0) && ((x & (1 << j)) == 0)) { isPalindrome = false; break; } else if (((x & (1 << i)) == 0) && ((x & (1 << j)) != 0)) { isPalindrome = false; break; } i++; j--; } // If the XOR of m and n is a palindrome, return // m if (isPalindrome) { return m; } } // If no such integer is found, return -1 return -1; } // Driver code public static void main(String[] args) { int n = 10; // Function call int largestPalXOR = largestPalindromeXOR(n); if (largestPalXOR == -1) { System.out.println("No such integer exists"); } else { System.out.println(largestPalXOR); } }}// This code is contributed by shivamgupta0987654321 |
Python3
import math# Function to find largest Integer# forming palindrome with ndef largestPalindromeXOR(n): # Find the number of bits in n numBits = int(math.log2(n)) + 1 # Iterate from the maximum possible # value of m down to 0 for m in range(n - 1, -1, -1): # Compute the XOR of m and n x = m ^ n # Check if the XOR of m and n is a palindrome i = 0 j = numBits - 1 isPalindrome = True while i < j: if x & (1 << i): if not (x & (1 << j)): isPalindrome = False break else: if x & (1 << j): isPalindrome = False break i += 1 j -= 1 # If the XOR of m and n is a palindrome, return m if isPalindrome: return m # If no such integer is found, return -1 return -1# Driver codeif __name__ == "__main__": n = 10 # Function call largestPalXOR = largestPalindromeXOR(n) if largestPalXOR == -1: print("No such integer exists") else: print(largestPalXOR)# This code is contributed by akshitaguprzj3 |
C#
// C# implementationusing System;class GFG { // Function to find largest Integer forming palindrome // with n public static int largestPalindromeXOR(int n) { // Find the number of bits in n int numBits = (int)(Math.Log(n) / Math.Log(2)) + 1; // Iterate from the maximum possible value of m down // to 0 for (int m = n - 1; m >= 0; m--) { // Compute the XOR of m and n int x = m ^ n; // Check if the XOR of m and n is a palindrome int i = 0, j = numBits - 1; bool isPalindrome = true; while (i < j) { if (((x & (1 << i)) != 0) && ((x & (1 << j)) == 0)) { isPalindrome = false; break; } else if (((x & (1 << i)) == 0) && ((x & (1 << j)) != 0)) { isPalindrome = false; break; } i++; j--; } // If the XOR of m and n is a palindrome, return // m if (isPalindrome) { return m; } } // If no such integer is found, return -1 return -1; } // Driver code public static void Main(string[] args) { int n = 10; // Function call int largestPalXOR = largestPalindromeXOR(n); if (largestPalXOR == -1) { Console.WriteLine("No such integer exists"); } else { Console.WriteLine(largestPalXOR); } }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript code for the above approach:// Function to find largest Integer// forming palindrome with nfunction largestPalindromeXOR(n) { // Find the number of bits in n let numBits = Math.floor(Math.log2(n)) + 1; // Iterate from the maximum possible // value of m down to 0 for (let m = n - 1; m >= 0; m--) { // Compute the XOR of m and n let x = m ^ n; // Check if the XOR of m and n // is a palindrome let i = 0, j = numBits - 1; let isPalindrome = true; while (i < j) { if (x & (1 << i)) { if (!(x & (1 << j))) { isPalindrome = false; break; } } else { if (x & (1 << j)) { isPalindrome = false; break; } } i++; j--; } // If the XOR of m and n is a // palindrome, return m if (isPalindrome) { return m; } } // If no such integer is found, // return -1 return -1;}// Driver codelet n = 10;// Function calllet largestPalXOR = largestPalindromeXOR(n);if (largestPalXOR == -1) { console.log("No such integer exists");} else { console.log(largestPalXOR);}// This code is contributed by Susobhan Akhuli |
Output
5
Time Complexity: O(n*logn)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
