Yet Another XOR Sort 2| Starters 78 Division 1|codechef (Rated till 6 stars)

Problem

You have an array �A with �N elements.

You can perform the following operation at most 20×�20×N times:

  • Select two indices �,�i,j satisfying ��≠��Ai​=Aj​, and set both ��Ai​ and ��Aj​ to ��⊕��Ai​⊕Aj​.
    Here, ⊕⊕ denotes the bitwise XOR operation.

Your goal is to make the final array sorted in non-decreasing order. Find a sequence of operations that achieves this.
It can be proven that a solution always exists.

Note that you don’t have to minimize the number of operations.

Input Format

  • The first line contains a single integer �T, denoting the number of test cases. Then the test cases follow.
  • Each test case consists of two lines of input.
    • The first line of each test case contains an integer �N — the size of the array �A.
    • The second line contains �N space-separated integers �1,�2,…,��A1​,A2​,…,AN​.

Output Format

  • For each test case, first print a single integer �K, the number of operations you performed.
  • Then, print �K lines each containing two integers. The integers on the �i-th line should be the indices you selected for the �i-th operation.

Constraints

  • 1≤�≤1041≤T≤104
  • 1≤�≤1051≤N≤105
  • 0≤��≤1090≤Ai​≤109
  • The sum of �N over all test cases won’t exceed 105105.

Sample 1:

Input

Output

2
4
34 40 20 30
3
1 2 3
2
1 4
1 3
0

Explanation:

Test case 11:

  • The array becomes [60,40,20,60][60,40,20,60] after the first operation. (Setting �1A1​ and �4A4​ to 34⊕3034⊕30)
  • The array becomes [40,40,40,60][40,40,40,60] after the second operation. (Setting �1A1​ and �3A3​ to 60⊕2060⊕20)

Test case 22:

  • The array is already sorted, so we don’t need to perform any operations.

Solution:

click on below image to get all solution link

Leave a Reply

Your email address will not be published. Required fields are marked *

यकीन नहीं मानोगे! ये 9 जगहें हैं UP में जो ताजमहल को भी फीका कर देंगी! मेरठ: इतिहास, धर्म और खूबसूरती का संगम! घूमने के लिए ये हैं बेहतरीन जगहें रोज आंवला खाने के 10 धांसू फायदे जो आपको कर देंगे हेल्दी और फिट! Anjali Arora to play Maa Sita: रामायण फिल्म में सीता का रोल निभाएंगी अंजली अरोड़ा, तैयारियों में लगी? Rinku Singh : रिंकू सिंह ने अपने दाहिने हाथ पर बने टैटू का खोला राज, सुनकर हो जायेंगे दंग Panchayat Season 3 Release Date: फुलेरा में मचा भूचाल! क्या अभिषेक इस बार हार जाएगा?