GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday 1 May 2022

Doubled Distances CodeChef Solution | CodeChef Problem Solution 2022

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

Formally, determine whether there exists a rearrangement of the given integers into an array [B1,B2,,BN] such that, for each 2iN1at least one of the following two conditions holds:

  • BiBi1=2(Bi+1Bi)or
  • 2(BiBi1)=Bi+1Bi

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, denoting the number of test cases. The description of T test cases follows.

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

Output Format

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

  • 1T100
  • 3N105
  • 0Ai109
  • The sum of N across all test cases won't exceed 105

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: Rearrange the numbers to form [5,4,2]. The consecutive differences are [45,24]=[1,2], and 2=2(1).

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

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

Join Now for Solution:- 

No comments:

Post a Comment