بالنظر إلى رقم n، فإن المهمة هي العثور على XOR من 1 إلى n.
أمثلة :
مدخل : ن = 6
الإخراج : 7
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7
مدخل : ن = 7
الإخراج :
// 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
النهج الساذج - O(ن) الوقت
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(1n+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
تعقيد الوقت: على)
المساحة المساعدة: يا(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++الرقم الثنائي-Repr XOR-من-1-إلى-n
1 1 [0001]
2 10 [0011]
3 11 [0000]<----- We get a 0
4100 [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)