Doubled Distances CodeChef Solution | CodeChef Problem Solution 2022

Doubled Distances CodeChef Solution | CodeChef Problem Solution 2022

You are given N$N$ integers {A1,A2,…,AN}$\{A_1,A_2,\dots ,A_N\}$. Determine whether they can be reordered such that each pair of consecutive differences differ by a factor of 2$2$.

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

• Bi−Bi−1=2⋅(Bi+1−Bi)$B_i-B_{i-1}=2\cdot (B_{i+1}-B_i)$, or
• 2⋅(Bi−Bi−1)=Bi+1−Bi$2\cdot (B_i-B_{i-1})=B_{i+1}-B_i$

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.

Solution Click Below:-  CLICK HERE

Input Format

• The first line of input will contain a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.

Chef and Gym CodeChef Solution | CodeChef Problem Solution 2022

Chef and Masks CodeChef Solution | CodeChef Problem Solution 2022

Game of Pooks CodeChef Solution | CodeChef Problem Solution 2022

Farmers League CodeChef Solution | CodeChef Problem Solution 2022

Doubled Distances CodeChef Solution | CodeChef Problem Solution 2022

Triple Inversions CodeChef Solution | CodeChef Problem Solution 2022

• Each test case consists of two lines of input.
• The first line of each test case contains a single integer, N$N$.
• The second line of each test case contains N$N$ space-separated integers, denoting A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Output Format

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

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

Constraints

• 1≤T≤100$1\le T\le 100$
• 3≤N≤105$3\le N\le {10}^5$
• 0≤Ai≤109$0\le A_i\le {10}^9$
• The sum of N$N$ across all test cases won't exceed 105${10}^5$

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

Explanation

Test case 1$1$: Rearrange the numbers to form [5,4,2]$[5,4,2]$. The consecutive differences are [4−5,2−4]=[−1,−2]$[4-5,2-4]=[-1,-2]$, and −2=2⋅(−1)$-2=2\cdot (-1)$.

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

Test case 3$3$: 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]$. 2$2$ and −4$-4$ do not differ by a factor of 2$2$ (they differ by a factor of −2$-2$), so this is not a valid arrangement.

Join Now for Solution:-