1–n szám XOR
Adott egy n szám, a feladat az XOR megkeresése 1-től n-ig.
Példák:
Bemenet: n = 6
Kimenet: 7
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7Bemenet: n = 7
Kimenet:
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
Naiv megközelítés – O(n) idő
1- Inicializálja az eredményt 0-ra.
1- Haladjon végig minden számon 1-től n-ig.
2- Végezze el a számok XOR-át egyenként az eredményekkel.
3- A végén adja vissza az eredményt.
// 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 ));
Kimenet
0
Időbeli összetettség: On)
Kiegészítő tér: O(1)
Várható megközelítés – O(1) idő
1- Keresse meg n maradékát 4-gyel modulálva.
2- Ha rem = 0, akkor az XOR ugyanaz, mint az n.
3- Ha rem = 1, akkor XOR 1 lesz.
4- Ha rem = 2, akkor XOR n+1 lesz.
5- Ha rem = 3, akkor XOR 0 lesz.
Ez hogy működik?
Amikor a számok XOR-jét végrehajtjuk, 0-t kapunk XOR értékként közvetlenül a 4 többszöröse előtt. Ez folyamatosan ismétlődik a 4 minden többszöröse előtt.
C++Szám Bináris-Repr XOR-1-től-n-ig
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 ?>
Kimenet
1
Időbeli összetettség: O(1)
Kiegészítő tér: O(1)
