[Solution] Doubled Distances solution codechef

Doubled Distances solution codechef – You are given NN integers {A1,A2,,AN}{A1,A2,…,AN}. Determine whether they can be reordered such that each pair of consecutive differences differ by a factor of 22.

[Solution] Doubled Distances solution codechef

Formally, determine whether there exists a rearrangement of the given integers into an array [B1,B2,,BN][B1,B2,…,BN] such that, for each 2iN12≤i≤N−1at least one of the following two conditions holds:

  • BiBi1=2(Bi+1Bi)Bi−Bi−1=2⋅(Bi+1−Bi)or
  • 2(BiBi1)=Bi+1Bi2⋅(Bi−Bi−1)=Bi+1−Bi

Note that different conditions can hold at different indices — the only restriction is that at each index, at least one of the given conditions must hold. Please see the sample tests below for examples.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of two lines of input.
  • The first line of each test case contains a single integer, NN.
  • The second line of each test case contains NN space-separated integers, denoting A1,A2,,ANA1,A2,…,AN.

[Solution] Doubled Distances solution codechef

For each test case, output in a single line the answer — 𝚈𝙴𝚂YES if a rearrangement that satisfies the given conditions exists, and 𝙽𝙾NO otherwise.

The output is not case sensitive, so for example the strings 𝚈𝙴𝚂, 𝚈𝚎𝚜, 𝚢𝙴𝚂YES, Yes, yES, etc. will all be treated as correct.

Constraints

  • 1T1001≤T≤100
  • 3N1053≤N≤105
  • 0Ai1090≤Ai≤109
  • The sum of NN across all test cases won’t exceed 105105

Sample Input 1 

4
3
5 2 4
5
2 1 16 8 4
5
97 98 100 96 88
6
16 19 18 21 24 22

Sample Output 1 

Yes
Yes
No
Yes

Doubled Distances solution Explanation

Test case 11: Rearrange the numbers to form [5,4,2][5,4,2]. The consecutive differences are [45,24]=[1,2][4−5,2−4]=[−1,−2], and 2=2(1)−2=2⋅(−1).

Test case 22: One possible rearrangement is [1,2,4,8,16][1,2,4,8,16]. The consecutive differences are consecutive powers of 22.

Test case 33: No rearrangement of the numbers satisfies the condition. For example, one rearrangement is [97,98,100,96,88][97,98,100,96,88] with consecutive differences [1,2,4,8][1,2,−4,−8]22 and 4−4 do not differ by a factor of 22 (they differ by a factor of 2−2), so this is not a valid arrangement.

For Solution

Click here

Leave a Comment