Given a value K which is the XOR of all the values from 1 to N, the task is to find the minimum value of N such that XOR from 1 to N is equal to K.
Examples:
Input: K = 7 Output: 6 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7 Input: K = 10 Output: Not Possible
Approach: This problem is similar to the Calculate XOR from 1 to n. Below are the conditions to be checked:
- If k = 0, then N = 3.
- If k = 1, then N = 1.
- If k % 4 = 0, then N = k.
- If k % 4 = 3, then N = k-1.
Below is the implementation of above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to find the value of Nint findN(int k){ // variable to store the result int ans; // handling case for '0' if (k == 0) ans = 3; // handling case for '1' if (k == 1) ans = 1; // when number is completely divided by // 4 then minimum 'x' will be 'k' else if (k % 4 == 0) ans = k; // when number divided by 4 gives 3 as // remainder then minimum 'x' will be 'k-1' else if (k % 4 == 3) ans = k - 1; // else it is not possible to get // k for any value of x else ans = -1; return ans;}// Driver codeint main(){ // let the given number be 7 int k = 7; int res = findN(k); if (res == -1) cout << "Not possible"; else cout << res; return 0;} |
Java
// Java implementation of// above approachimport java.io.*;class GFG{// Function to find the // value of Nstatic int findN(int k){ // variable to store // the result int ans; // handling case for '0' if (k == 0) ans = 3; // handling case for '1' if (k == 1) ans = 1; // when number is completely // divided by 4 then minimum // 'x' will be 'k' else if (k % 4 == 0) ans = k; // when number divided by 4 // gives 3 as remainder then // minimum 'x' will be 'k-1' else if (k % 4 == 3) ans = k - 1; // else it is not possible to // get k for any value of x else ans = -1; return ans;}// Driver codepublic static void main (String[] args) { // let the given number be 7 int k = 7; int res = findN(k); if (res == -1) System.out.println("Not possible"); else System.out.println(res);}}// This code is contributed// by inder_verma |
Python3
# Python3 implementation of# above approach # Function to find the value of N def findN(k) : # handling case for '0' if (k == 0) : ans = 3 # handling case for '1' if (k == 1) : ans = 1 # when number is completely # divided by 4 then minimum # 'x' will be 'k' elif (k % 4 == 0) : ans = k # when number divided by 4 # gives 3 as remainder then # minimum 'x' will be 'k-1' elif (k % 4 == 3) : ans = k - 1 # else it is not possible to # get k for any value of x else: ans = -1 return ans # Driver code # let the given number be 7 k = 7res = findN(k) if (res == -1): print("Not possible") else: print(res)# This code is contributed# by Smitha |
C#
// C# implementation of// above approachusing System;class GFG{// Function to find the // value of Nstatic int findN(int k){ // variable to store // the result int ans; // handling case for '0' if (k == 0) ans = 3; // handling case for '1' if (k == 1) ans = 1; // when number is completely // divided by 4 then minimum // 'x' will be 'k' else if (k % 4 == 0) ans = k; // when number divided by 4 // gives 3 as remainder then // minimum 'x' will be 'k-1' else if (k % 4 == 3) ans = k - 1; // else it is not possible to // get k for any value of x else ans = -1; return ans;}// Driver codepublic static void Main () { // let the given number be 7 int k = 7; int res = findN(k); if (res == -1) Console.WriteLine("Not possible"); else Console.WriteLine(res);}}// This code is contributed// by inder_verma |
PHP
<?php// PHP implementation of above approach// Function to find the value of Nfunction findN($k){ // variable to store the result $ans; // handling case for '0' if ($k == 0) $ans = 3; // handling case for '1' if ($k == 1) $ans = 1; // when number is completely divided // by 4 then minimum 'x' will be 'k' else if ($k % 4 == 0) $ans = $k; // when number divided by 4 gives 3 as // remainder then minimum 'x' will be 'k-1' else if ($k % 4 == 3) $ans = $k - 1; // else it is not possible to // get k for any value of x else $ans = -1; return $ans;}// Driver code// let the given number be 7$k = 7;$res = findN($k);if ($res == -1) echo "Not possible";else echo $res;// This code is contributed by Mahadev?> |
Javascript
<script>// javascript implementation of// above approach// Function to find the // value of Nfunction findN(k){ // variable to store // the result var ans; // handling case for '0' if (k == 0) ans = 3; // handling case for '1' if (k == 1) ans = 1; // when number is completely // divided by 4 then minimum // 'x' will be 'k' else if (k % 4 == 0) ans = k; // when number divided by 4 // gives 3 as remainder then // minimum 'x' will be 'k-1' else if (k % 4 == 3) ans = k - 1; // else it is not possible to // get k for any value of x else ans = -1; return ans;}// Driver code// let the given number be 7var k = 7;var res = findN(k);if (res == -1) document.write("Not possible");else document.write(res);// This code contributed by shikhasingrajput </script> |
Output:
6
Time Complexity: O(1)
Auxiliary Space: O(1)
How does this work?
When we do XOR of numbers, we get 0 as XOR value just before a multiple of 4. This keeps repeating before every multiple of 4.
Number Binary-Repr XOR-from-1-to-n 1 1 [0001] 2 10 [0011] 3 11 [0000] <----- We get a 0 4 100 [0100] <----- Equals to n 5 101 [0001] 6 110 [0111] 7 111 [0000] <----- We get 0 8 1000 [1000] <----- Equals to n 9 1001 [0001] 10 1010 [1011] 11 1011 [0000] <------ We get 0 12 1100 [1100] <------ Equals to n
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!
