Dado un número n, la tarea es encontrar el XOR de 1 a n.
Ejemplos:
Input : n = 6 Output : 7 // 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7 Input : n = 7 Output : 0 // 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
Método 1 (enfoque ingenuo):
1- Inicializa el resultado como 0.
1- Recorre todos los números del 1 al n.
2- Haz XOR de números uno por uno con resultados.
3- Al final, devolver el resultado.
C++
// C++ program to find XOR of numbers
// from 1 to n.
#include <bits/stdc++.h>
using namespace std;
int computeXOR(int n)
{
if (n == 0)
return 0; // base case
int uni = 0;
for (int i = 1; i <= n; i++) {
uni = uni ^ i; // calculate XOR
}
return uni;
}
int main()
{
int n = 7;
int result = computeXOR(n);
cout << result << endl;
return 0;
}
/* This code is contributed by Rishab Dugar */
Java
// Given a number n, find the XOR from 1 to n for given n number
import java.io.*;
public class GFG {
public static void main(String[] args) {
int n = 7;
int ans = computeXor(n);
System.out.println(ans);
}
static int computeXor(int n){
if(n == 0) return 0; // base case
int uni = 0;
for (int i = 1; i <= n; i++) {
uni = uni^i; // calculate XOR
}
return uni;
}
}
/* This code is contributed by devendra salunke */
Python3
#defining a function computeXOR def computeXOR(n): uni = 0 if n==0: return 0 #base case for i in range(1,n+1): uni = uni ^ i return uni n = 7 ans = computeXOR(n) #calling the function print(ans) #This code is contributed by Gayatri Deshmukh
C#
// C# program that finds the XOR
// from 1 to n for a given number n
using System;
public class GFG {
static int computeXor(int n)
{
if (n == 0)
return 0; // base case
int uni = 0;
for (int i = 1; i <= n; i++) {
uni = uni ^ i; // calculate XOR
}
return uni;
}
// Driver code
public static void Main(string[] args)
{
int n = 7;
// Function call
int ans = computeXor(n);
Console.WriteLine(ans);
}
}
// This code is contributed by phasing17
Javascript
// JavaScript that for a number n
// finds the XOR from 1 to n for given n number
function computeXor(n){
if(n == 0)
return 0; // base case
var uni = 0;
for (var i = 1; i <= n; i++)
uni = uni^i; // calculate XOR
return uni;
}
// Driver Code
var n = 7;
// Function Call
var ans = computeXor(n);
console.log(ans);
// This code is contributed by phasing17
Producción
0
Método 2 (Método eficiente):
1- Encuentra el resto de n modulándolo con 4.
2- Si rem = 0, entonces XOR será igual a n.
3- Si rem = 1, entonces XOR será 1.
4- Si rem = 2, entonces XOR será n+1.
5- Si rem = 3, entonces XOR será 0.
C++
// C++ program to find XOR of numbers
// from 1 to n.
#include<bits/stdc++.h>
using namespace std;
// Method to calculate xor
int computeXOR(int n)
{
// If n is a multiple of 4
if (n % 4 == 0)
return n;
// If n%4 gives remainder 1
if (n % 4 == 1)
return 1;
// If n%4 gives remainder 2
if (n % 4 == 2)
return n + 1;
// If n%4 gives remainder 3
return 0;
}
// Driver method
int main()
{
int n = 5;
cout<<computeXOR(n);
}
// This code is contributed by rutvik_56.
Java
// Java program to find XOR of numbers
// from 1 to n.
class GFG
{
// Method to calculate xor
static int computeXOR(int n)
{
// If n is a multiple of 4
if (n % 4 == 0)
return n;
// If n%4 gives remainder 1
if (n % 4 == 1)
return 1;
// If n%4 gives remainder 2
if (n % 4 == 2)
return n + 1;
// If n%4 gives remainder 3
return 0;
}
// Driver method
public static void main (String[] args)
{
int n = 5;
System.out.println(computeXOR(n));
}
}
Python 3
# Python 3 Program to find # XOR of numbers from 1 to n. # Function to calculate xor def computeXOR(n) : # Modulus operator are expensive # on most of the computers. n & 3 # will be equivalent to n % 4. # if n is multiple of 4 if n % 4 == 0 : return n # If n % 4 gives remainder 1 if n % 4 == 1 : return 1 # If n%4 gives remainder 2 if n % 4 == 2 : return n + 1 # If n%4 gives remainder 3 return 0 # Driver Code if __name__ == "__main__" : n = 5 # function calling print(computeXOR(n)) # This code is contributed by ANKITRAI1
C#
// C# program to find XOR
// of numbers from 1 to n.
using System;
class GFG
{
// Method to calculate xor
static int computeXOR(int n)
{
// If n is a multiple of 4
if (n % 4 == 0)
return n;
// If n%4 gives remainder 1
if (n % 4 == 1)
return 1;
// If n%4 gives remainder 2
if (n % 4 == 2)
return n + 1;
// If n%4 gives remainder 3
return 0;
}
// Driver Code
static public void Main ()
{
int n = 5;
Console.WriteLine(computeXOR(n));
}
}
// This code is contributed by ajit
PHP
<?php
// PHP program to find XOR
// of numbers from 1 to n.
// Function to calculate xor
function computeXOR($n)
{
// Modulus operator are expensive
// on most of the computers. n & 3
// will be equivalent to n % 4.
switch($n & 3) // n % 4
{
// if n is multiple of 4
case 0: return $n;
// If n % 4 gives remainder 1
case 1: return 1;
// If n % 4 gives remainder 2
case 2: return $n + 1;
// If n % 4 gives remainder 3
case 3: return 0;
}
}
// Driver code
$n = 5;
echo computeXOR($n);
// This code is contributed by aj_36
?>
Javascript
<script>
// JavaScript program to find XOR of numbers
// from 1 to n.
// Function to calculate xor
function computeXOR(n)
{
// Modulus operator are expensive on most of the
// computers. n & 3 will be equivalent to n % 4.
// if n is multiple of 4
if(n % 4 == 0)
return n;
// If n % 4 gives remainder 1
if(n % 4 == 1)
return 1;
// If n % 4 gives remainder 2
if(n % 4 == 2)
return n + 1;
// If n % 4 gives remainder 3
if(n % 4 == 3)
return 0;
}
// Driver code
// your code goes here
let n = 5;
document.write(computeXOR(n));
// This code is constributed by Surbhi Tyagi.
</script>
Producción
1
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
¿Como funciona esto?
Cuando hacemos XOR de números, obtenemos 0 como el 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
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA