XOR von 1 bis n Zahlen
Bei einer gegebenen Zahl n besteht die Aufgabe darin, das XOR von 1 bis n zu finden.
Beispiele:
Eingabe: n = 6
Ausgabe : 7
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7Eingabe: n = 7
Ausgabe :
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
Naiver Ansatz – O(n) Zeit
1- Initialisieren Sie das Ergebnis als 0.
1- Durchlaufen Sie alle Zahlen von 1 bis n.
2- Führen Sie eine XOR-Verknüpfung der Zahlen nacheinander mit den Ergebnissen durch.
3- Geben Sie am Ende das Ergebnis zurück.
// C++ program to find XOR of numbers // from 1 to n. #include using namespace std ; int computeXOR ( int n ) { int res = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { res = res ^ i ; } return res ; } int main () { int n = 7 ; cout < < computeXOR ( n ) < < endl ; return 0 ; }
Java // Given a number n find the XOR from 1 to n for given n number import java.io.* ; public class GfG { static int computeXor ( int n ){ int res = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { res = res ^ i ; } return res ; } public static void main ( String [] args ) { int n = 7 ; System . out . println ( computeXor ( n )); } }
Python #defining a function computeXOR def computeXOR ( n ): res = 0 for i in range ( 1 n + 1 ): res = res ^ i return res n = 7 print ( computeXOR ( n ))
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 ) { int res = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { res = res ^ i ; // calculate XOR } return res ; } // 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 ){ var res = 0 ; for ( let i = 1 ; i <= n ; i ++ ) res = res ^ i ; // calculate XOR return res ; } // Driver Code let n = 7 ; console . log ( computeXor ( n ));
Ausgabe
0
Zeitkomplexität: An)
Hilfsraum: O(1)
Erwarteter Ansatz – O(1)-Zeit
1- Finden Sie den Rest von n, indem Sie ihn mit 4 modulieren.
2- Wenn rem = 0, dann ist XOR dasselbe wie n.
3- Wenn rem = 1, dann ist XOR 1.
4- Wenn rem = 2, dann ist XOR n+1.
5- Wenn rem = 3, dann ist XOR 0.
Wie funktioniert das?
Wenn wir Zahlen XOR-verknüpfen, erhalten wir 0 als XOR-Wert direkt vor einem Vielfachen von 4. Dies wiederholt sich immer wieder vor jedem Vielfachen von 4.
C++Zahl Binär-Repr XOR-von-1-bis-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
// C++ program to find XOR of numbers // from 1 to n. #include 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
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>
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 ?>
Ausgabe
1
Zeitkomplexität: O(1)
Hilfsraum: O(1)
