XOR від 1 до n чисел
Для числа n завдання полягає в тому, щоб знайти XOR від 1 до n.
Приклади:
Вхідні дані: n = 6
Вихід: 7
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7Вхідні дані: n = 7
Вихід:
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
Наївний підхід - O(n) Time
1- Ініціалізувати результат як 0.
1- Обійти всі числа від 1 до n.
2- Виконуйте XOR чисел одне за одним з результатами.
3- В кінці поверніть результат.
// 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 ));
Вихід
0
Часова складність: O(n)
Допоміжний простір: О(1)
Очікуване наближення - O(1) Час
1- Знайдіть залишок від n, помноживши його на 4.
2- Якщо rem = 0, тоді XOR буде таким самим, як n.
3- Якщо rem = 1, тоді XOR буде 1.
4- Якщо rem = 2, тоді XOR буде n+1.
5- Якщо rem = 3, тоді XOR буде 0.
Як це працює?
Коли ми виконуємо XOR чисел, ми отримуємо 0 як значення XOR безпосередньо перед кратним 4. Це постійно повторюється перед кожним кратним 4.
C++Число 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
// 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 ?>
Вихід
1
Часова складність: О(1)
Допоміжний простір: О(1)
