1'den n'ye Sayıların XOR'u
Bir n sayısı verildiğinde görev, 1'den n'ye kadar olan XOR'u bulmaktır.
Örnekler:
Giriş: n = 6
Çıkış: 7
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7Giriş : n = 7
Çıkış:
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
Naif Yaklaşım - O(n) Zaman
1- Sonucu 0 olarak sıfırlayın.
1- 1'den n'ye kadar olan tüm sayıları çaprazlayın.
2- Sonuçları içeren sayıların XOR'unu tek tek yapın.
3- Sonunda sonucu döndürün.
// 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 ));
Çıkış
0
Zaman Karmaşıklığı: Açık)
Yardımcı Alan: Ç(1)
Beklenen Yaklaşma - O(1) Zaman
1- n'nin kalanını 4 ile modüle ederek bulun.
2- Rem = 0 ise XOR, n ile aynı olacaktır.
3- Rem = 1 ise XOR 1 olacaktır.
4- rem = 2 ise XOR n+1 olacaktır.
5- Rem = 3 ise XOR 0 olacaktır.
Bu nasıl çalışır?
Sayıların XOR'unu yaptığımızda 4'ün katının hemen öncesindeki XOR değeri olarak 0 elde ederiz. Bu, 4'ün her katından önce tekrarlanır.
C++Sayı İkili Repr XOR-1'den n'ye
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 ?>
Çıkış
1
Zaman Karmaşıklığı: Ç(1)
Yardımcı Alan: Ç(1)
