You are given an array 𝐴A of size 𝑁N.You can rearrange the elements of 𝐴A as you want. After that, construct an array 𝐵B of size 𝑁N as:𝐵1=𝐴1B 1 =A 1 ;𝐵𝑖=𝐵𝑖−1⊕𝐴𝑖B i =B i−1 ⊕A i for all 2≤𝑖≤𝑁2≤i≤N, where ⊕⊕ denotes the bitwise XOR operator.Find a rearrangement of 𝐴A such that 𝐵𝑖≠0B i =0 for all 1≤𝑖≤𝑁1≤i≤N.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of multiple lines of input.The first line of each test case contains 𝑁N, the size of the array 𝐴A.The second line of each test case contains 𝑁N space-separated integers : 𝐴1,𝐴2,…,𝐴𝑁A 1 ,A 2 ,…,A N .Output FormatFor each test case, output on a new line, 𝑁N space-separated integers denoting the rearrangement of 𝐴A satisfying the conditions.In case no such rearrangement exists, print −1−1 instead.Constraints1≤𝑇≤2⋅1041≤T≤2⋅10 4 1≤𝑁≤2⋅1051≤N≤2⋅10 5 1≤𝐴𝑖≤1091≤A i ≤10 9 The sum of 𝑁N over all test cases does not exceed 2⋅1052⋅10 5 .Sample 1:InputOutput431 2 351 2 3 4 531 2 211-11 2 4 3 51 2 21Explanation:Test case 11 : It can be shown that it's impossible to rearrange 𝐴A in a valid way.Test case 22 : A possible rearrangement of array 𝐴A is [1,2,4,3,5][1,2,4,3,5] and the corresponding array 𝐵B is [1,3,7,4,1][1,3,7,4,1]. Here 𝐵𝑖≠0B i =0 for all 1≤𝑖≤𝑁1≤i≤N.
Question
You are given an array 𝐴A of size 𝑁N.You can rearrange the elements of 𝐴A as you want. After that, construct an array 𝐵B of size 𝑁N as:𝐵1=𝐴1B 1 =A 1 ;𝐵𝑖=𝐵𝑖−1⊕𝐴𝑖B i =B i−1 ⊕A i for all 2≤𝑖≤𝑁2≤i≤N, where ⊕⊕ denotes the bitwise XOR operator.Find a rearrangement of 𝐴A such that 𝐵𝑖≠0B i =0 for all 1≤𝑖≤𝑁1≤i≤N.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of multiple lines of input.The first line of each test case contains 𝑁N, the size of the array 𝐴A.The second line of each test case contains 𝑁N space-separated integers : 𝐴1,𝐴2,…,𝐴𝑁A 1 ,A 2 ,…,A N .Output FormatFor each test case, output on a new line, 𝑁N space-separated integers denoting the rearrangement of 𝐴A satisfying the conditions.In case no such rearrangement exists, print −1−1 instead.Constraints1≤𝑇≤2⋅1041≤T≤2⋅10 4 1≤𝑁≤2⋅1051≤N≤2⋅10 5 1≤𝐴𝑖≤1091≤A i ≤10 9 The sum of 𝑁N over all test cases does not exceed 2⋅1052⋅10 5 .Sample 1:InputOutput431 2 351 2 3 4 531 2 211-11 2 4 3 51 2 21Explanation:Test case 11 : It can be shown that it's impossible to rearrange 𝐴A in a valid way.Test case 22 : A possible rearrangement of array 𝐴A is [1,2,4,3,5][1,2,4,3,5] and the corresponding array 𝐵B is [1,3,7,4,1][1,3,7,4,1]. Here 𝐵𝑖≠0B i =0 for all 1≤𝑖≤𝑁1≤i≤N.
Solution
Para resolver este problema, sigamos los siguientes pasos:
- Leer el número de casos de prueba, T.
- Para cada caso de prueba:
- Leer el tamaño del array, N.
- Leer el array A de tamaño N.
- Intentar encontrar una reordenación de A tal que el array B construido cumpla con la condición para todo .
Pasos detallados:
- Leer el número de casos de prueba, T.
- Para cada caso de prueba:
- Leer el tamaño del array, N.
- Leer el array A de tamaño N.
- Si N es 1, entonces B siempre será igual a A, y si A[0] es 0, no hay solución.
- Ordenar el array A.
- Construir el array B usando la definición dada:
- para
- Verificar si todos los elementos de B son diferentes de 0.
- Si se cumple la condición, imprimir la reordenación de A.
- Si no se cumple, imprimir -1.
Implementación:
def solve():
import sys
input = sys.stdin.read
data = input().split()
index = 0
T = int(data[index])
index += 1
results = []
for _ in range(T):
N = int(data[index])
index += 1
A = list(map(int, data[index:index + N]))
index += N
if N == 1:
if A[0] == 0:
results.append("-1")
else:
results.append(str(A[0]))
continue
A.sort()
B = [0] * N
Similar Questions
You are given an array 𝐴A of size 𝑁N.You can rearrange the elements of 𝐴A as you want. After that, construct an array 𝐵B of size 𝑁N as:𝐵1=𝐴1B 1 =A 1 ;𝐵𝑖=𝐵𝑖−1B i =B i−1 && 𝐴𝑖A i for all 2≤𝑖≤𝑁2≤i≤N, where && denotes the bitwise AND operator.Find the lexicographically largest possible array 𝐵B.For two arrays 𝑋X and 𝑌Y, both of size 𝑁N, the array 𝑋X is said to be lexicographically larger than array 𝑌Y, if, in the first position where 𝑋X and 𝑌Y differ, 𝑋𝑖>𝑌𝑖X i >Y i .Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of multiple lines of input.The first line of each test case contains 𝑁N, the size of the array 𝐴A.The second line of each test case contains 𝑁N space-separated integers 𝐴1,𝐴2,…,𝐴𝑁A 1 ,A 2 ,…,A N .Output FormatFor each test case, output on a new line, 𝑁N space separated integers denoting the lexicographically largest array 𝐵B that can be formed by any rearrangement of 𝐴A.Constraints1≤𝑇≤2⋅1041≤T≤2⋅10 4 1≤𝑁≤2⋅1051≤N≤2⋅10 5 1≤𝐴𝑖≤1091≤A i ≤10 9 The sum of 𝑁N over all test cases does not exceed 2⋅1052⋅10 5 .
You are given two distinct non-negative integers x𝑥 and y𝑦. Consider two infinite sequences a1,a2,a3,…𝑎1,𝑎2,𝑎3,… and b1,b2,b3,…𝑏1,𝑏2,𝑏3,…, wherean=n⊕x𝑎𝑛=𝑛⊕𝑥;bn=n⊕y𝑏𝑛=𝑛⊕𝑦.Here, x⊕y𝑥⊕𝑦 denotes the bitwise XOR operation of integers x𝑥 and y𝑦.For example, with x=6𝑥=6, the first 88 elements of sequence a𝑎 will look as follows: [7,4,5,2,3,0,1,14,…][7,4,5,2,3,0,1,14,…]. Note that the indices of elements start with 11.Your task is to find the length of the longest common subsegment†† of sequences a𝑎 and b𝑏. In other words, find the maximum integer m𝑚 such that ai=bj,ai+1=bj+1,…,ai+m−1=bj+m−1𝑎𝑖=𝑏𝑗,𝑎𝑖+1=𝑏𝑗+1,…,𝑎𝑖+𝑚−1=𝑏𝑗+𝑚−1 for some i,j≥1𝑖,𝑗≥1.††A subsegment of sequence p𝑝 is a sequence pl,pl+1,…,pr𝑝𝑙,𝑝𝑙+1,…,𝑝𝑟, where 1≤l≤r1≤𝑙≤𝑟.InputEach test consists of multiple test cases. The first line contains a single integer t𝑡 (1≤t≤1041≤𝑡≤104) — the number of test cases. The description of the test cases follows.The only line of each test case contains two integers x𝑥 and y𝑦 (0≤x,y≤109,x≠y0≤𝑥,𝑦≤109,𝑥≠𝑦) — the parameters of the sequences.OutputFor each test case, output a single integer — the length of the longest common subsegment.ExampleinputCopy40 112 457 37316560849 14570961outputCopy18433554432NoteIn the first test case, the first 77 elements of sequences a𝑎 and b𝑏 are as follows:a=[1,2,3,4,5,6,7,…]𝑎=[1,2,3,4,5,6,7,…]b=[0,3,2,5,4,7,6,…]𝑏=[0,3,2,5,4,7,6,…]It can be shown that there isn't a positive integer k𝑘 such that the sequence [k,k+1][𝑘,𝑘+1] occurs in b𝑏 as a subsegment. So the answer is 11.In the third test case, the first 2020 elements of sequences a𝑎 and b𝑏 are as follows:a=[56,59,58,61,60,63,62,49,48,51,50,53,52,55,54,41, 40, 43, 42,45,…]𝑎=[56,59,58,61,60,63,62,49,48,51,50,53,52,55,54,41, 40, 43, 42,45,…]b=[36,39,38,33,32,35,34,45,44,47,46,41, 40, 43, 42,53,52,55,54,49,…]𝑏=[36,39,38,33,32,35,34,45,44,47,46,41, 40, 43, 42,53,52,55,54,49,…]It can be shown that one of the longest common subsegments is the subsegment [41,40,43,42][41,40,43,42] with a length of 44.
You are given an array 𝐴A of length 𝑁N, and an integer 𝐾K.You can perform the following operation:Choose any index 𝑖i (1≤𝑖≤𝑁1≤i≤N), and increase 𝐴𝑖A i by 𝐾K.Find the minimum possible value of max(𝐴)−min(𝐴)max(A)−min(A) attainable, if you can perform this operation as many times as you like (possibly, zero times).Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of two lines of input.The first line of each test case contains two space-separated integers 𝑁N and 𝐾K — the length of the array and the parameter 𝐾K.The second line contains 𝑁N space-separated integers 𝐴1,𝐴2,…,𝐴𝑁A 1 ,A 2 ,…,A N — the initial values of the array elements.Output FormatFor each test case, output on a new line the answer: the minimum possible value of max(𝐴)−min(𝐴)max(A)−min(A) if you can perform the given operation any number of times.Constraints1≤𝑇≤1051≤T≤10 5 1≤𝑁≤2⋅1051≤N≤2⋅10 5 1≤𝐾≤1091≤K≤10 9 1≤𝐴𝑖≤1091≤A i ≤10 9 The sum of 𝑁N over all test cases won't exceed 2⋅1052⋅10 5 .Sample 1:InputOutput43 41 5 43 212 8 44 11 43 62 8256 121 2 4 128 130 1311008Explanation:Test case 11: Increase the first element by 𝐾=4K=4 to obtain the array [5,5,4][5,5,4].Here, max−min=5−4=1max−min=5−4=1, which is the best possible.Test case 22: The second and third elements can be increased by 22 till they reach 1212, at which point all the elements of the array are equal, so max(𝐴)−min(𝐴)=0max(A)−min(A)=0.Test case 33: Since 𝐾=1K=1, again it's possible to make all the elements equal.Test case 44: Do the following:Increase 𝐴1A 1 by 1212 repeatedly to make it 133133.Increase 𝐴2A 2 by 1212 repeatedly to make it 134134.Increase 𝐴3A 3 by 1212 repeatedly to make it 136136.The array is now [133,134,136,128,130,131][133,134,136,128,130,131].For this array, max(𝐴)−min(𝐴)=136−128=8max(A)−min(A)=136−128=8.It can be shown that this is optimal.
You are given an array of integers. Find the XOR of all the pairwise sums formed by the elements of the array.Input FormatThe first line of input contains T - the number of test cases. It is followed by 2T lines, the first line contains N - the size of the array. The second line contains the elements of the array.Output FormatFor each test case, print the XOR product of all the pairwise sums of the elements from the array, separated by a newline.Constraints10 points1 <= T <= 1001 <= N <= 10000 <= A[i] <= 10540 points1 <= T <= 1001 <= N <= 1050 <= A[i] <= 105ExampleInput254 10 54 11 8615 35 25 10 15 12Output118120ExplanationTest-Case 1All the pairwise sums formed with 4 are (4 + 4), (4 + 10), (4 + 54), (4 + 11), (4 + 8) = 8, 14, 58, 15, 12All the pairwise sums formed with 10 are (10 + 4), (10 + 10), (10 + 54), (10 + 11), (10 + 8) = 14, 20, 64, 21, 18All the pairwise sums formed with 54 are (54 + 4), (54 + 10), (54 + 54), (54 + 11), (54 + 8) = 58, 64, 108, 65, 62All the pairwise sums formed with 11 are (11 + 4), (11 + 10), (11 + 54), (11 + 11), (11 + 8) = 15, 21, 65, 22, 19All the pairwise sums formed with 8 are (8 + 4), (8 + 10), (8 + 54), (8 + 11), (8 + 8) = 12, 18, 62, 19, 16XOR of all the above sums = (8 ^ 14 ^ 58 ^ 15 ^ 12) ^ (14 ^ 20 ^ 64 ^ 21 ^ 18) ^ (58 ^ 64 ^ 108 ^ 65 ^ 62) ^ (15 ^ 21 ^ 65 ^ 22 ^ 19) ^ (12 ^ 18 ^ 62 ^ 19 ^ 16) = 118
You are given an array nums, where each number in the array appears either once or twice.Return the bitwise XOR of all the numbers that appear twice in the array, or 0 if no number appears twice. Example 1:Input: nums = [1,2,1,3]Output: 1Explanation:The only number that appears twice in nums is 1.Example 2:Input: nums = [1,2,3]Output: 0Explanation:No number appears twice in nums.Example 3:Input: nums = [1,2,2,1]Output: 3Explanation:Numbers 1 and 2 appeared twice. 1 XOR 2 == 3. Constraints:1 <= nums.length <= 501 <= nums[i] <= 50Each number in nums appears either once or twice.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.