Dado un valor K que es el XOR de todos los valores de 1 a N, la tarea es encontrar el valor mínimo de N tal que XOR de 1 a N sea igual a K.
Ejemplos :
Input: K = 7 Output: 6 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7 Input: K = 10 Output: Not Possible
Enfoque: Este problema es similar a Calcular XOR de 1 a n . A continuación se detallan las condiciones a comprobar:
- Si k = 0, entonces N = 3.
- Si k = 1, entonces N = 1.
- Si k % 4 = 0, entonces N = k.
- Si k % 4 = 3, entonces N = k-1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the value of N
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 code
int 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 approach
import java.io.*;
class GFG
{
// Function to find the
// value of N
static 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 code
public 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 = 7
res = findN(k)
if (res == -1):
print("Not possible")
else:
print(res)
# This code is contributed
# by Smitha
C#
// C# implementation of
// above approach
using System;
class GFG
{
// Function to find the
// value of N
static 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 code
public 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 N
function 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 N
function 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 7
var k = 7;
var res = findN(k);
if (res == -1)
document.write("Not possible");
else
document.write(res);
// This code contributed by shikhasingrajput
</script>
Producción:
6
¿Como funciona esto?
Cuando hacemos XOR de números, obtenemos 0 como valor XOR justo antes de un múltiplo de 4. Esto sigue repitiéndose antes de cada múltiplo de 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