Find smallest number n such that n XOR n+1 equals to given k.
You are given a positive number k, we need to find a positive integer n, such that XOR of n and n+1 is equal to k. If no such n exist then print -1.
Examples:
Input : 3 Output : 1 Input : 7 Output : 3 Input : 6 Output : -1
Below are two cases when we do n XOR (n+1) for a number n.
Case 1 : n is even. Last bit of n is 0 and last bit of (n+1) is 1. Rest of the bits are same in both. So XOR would always be 1 if n is even.
Case : n is odd Last bit in n is 1. And in n+1, last bit is 0. But in this case there may be more bits which differ due to carry. The carry continues to propagate to left till we find first 0 bit. So n XOR n+1 will we 2^i-1 where i is the position of first 0 bit in n from left. So, we can say that if k is of form 2^i-1 then we will have our answer as k/2.
Finally our steps are:
If we have k=1, answer = 2 [We need smallest positive n] Else If k is of form 2^i-1, answer = k/2, else, answer = -1
C++
C
// C to find n such that XOR of n and n+1 is equals to given n #include <stdio.h> // function to return the required n int xorCalc( int k) { if (k == 1) return 2; // if k is of form 2^i-1 if (((k + 1) & k) == 0) return k / 2; return -1; } // driver program int main() { int k = 31; printf ( "%d" ,xorCalc(k)); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java to find n such that XOR of n and n+1 // is equals to given n class GFG { // function to return the required n static int xorCalc( int k) { if (k == 1 ) return 2 ; // if k is of form 2^i-1 if (((k + 1 ) & k) == 0 ) return k / 2 ; return 1 ; } // Driver code public static void main(String[] args) { int k = 31 ; System.out.println(xorCalc(k)); } } // This code is contributed by Aditya Kumar (adityakumar129) |
Python3
C#
// C# to find n such that XOR // of n and n+1 is equals to // given n using System; class GFG { // function to return the required // n static int xorCalc( int k) { if (k == 1) return 2; // if k is of form 2^i-1 if (((k + 1) & k) == 0) return k / 2; return 1; } // Driver code public static void Main () { int k = 31; Console.WriteLine(xorCalc(k)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP to find n such // that XOR of n and n+1 // is equals to given n // function to return // the required n function xorCalc( $k ) { if ( $k == 1) return 2; // if k is of form 2^i-1 if ((( $k + 1) & $k ) == 0) return floor ( $k / 2); return 1; } // Driver Code $k = 31; echo xorCalc( $k ); // This code is contributed by vt_m. ?> |
Javascript
<script> // Javascript to find n such that XOR of n and n+1 // is equals to given n // function to return the required n function xorCalc(k) { if (k == 1) return 2; // if k is of form 2^i-1 if (((k + 1) & k) == 0) return parseInt(k / 2); return 1; } // driver program var k = 31; document.write( xorCalc(k)); // This code is contributed by itsok. </script> |
Output:
15
Time Complexity : O(1)
Auxiliary Space : O(1)