XOR od 1 do n čísel
Ak je dané číslo n, úlohou je nájsť XOR od 1 do n.
Príklady:
Vstup: n = 6
výstup: 7
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7Vstup: n = 7
výstup:
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
Naivný prístup – O(n) Time
1- Inicializujte výsledok ako 0.
1- Prejdite všetky čísla od 1 do n.
2- Urobte XOR čísel jedno po druhom s výsledkami.
3- Na konci vráťte výsledok.
// 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 ));
Výstup
0
Časová zložitosť: O(n)
Pomocný priestor: O(1)
Očakávaný prístup – čas O(1).
1- Nájdite zvyšok n moduláciou pomocou 4.
2- Ak rem = 0, potom XOR bude rovnaké ako n.
3- Ak rem = 1, XOR bude 1.
4- Ak rem = 2, potom XOR bude n+1.
5- Ak rem = 3, XOR bude 0.
Ako to funguje?
Keď urobíme XOR čísel, dostaneme 0 ako hodnotu XOR tesne pred násobkom 4. Toto sa neustále opakuje pred každým násobkom 4.
C++Číslo Binary-Repr XOR-od-1-do-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 ?>
Výstup
1
Časová zložitosť: O(1)
Pomocný priestor: O(1)
