Last Updated: 15 Nov, 2021

Array Of Doubled Pair

Moderate

Solve now

Problem statement

Alice and Bob were playing the game. Alice challenged to bob to solve the following problem. The problem description is as follows:

Given an integer array 'ARR' of even length 'N', find if it is possible to reorder the array such that such that 'ARR[2 * i + 1]' = 2 * 'ARR[2 * i]' for every 0 <= 'i' < 'N' / 2.

Your task is to help bob to solve the task given by Alice to him.

EXAMPLE:

Input: ARR = [4, 3, 2, 6]
Output: true

Explanation: Given array can be transformed like this [3, 6, 2, 4] which follows the rule 'ARR[2 * i + 1]' = 2 * 'ARR[2 * i]' for every 0 <= i < 'N' / 2.

Input Format :

The first line of input contains an integer ‘T', denoting the number of test cases. 

The first line of each test case contains a single integer 'N' representing the size of the input array ‘ARR’. 

The second line of each test case contains 'N' integers ‘ARR’, denoting the initial arrangement of the given array.

Output format :

For each test case, print "true" if Bob can win the challenge against Alice or else print "false".

Output for each test case will be printed in a separate line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 10
1 <= 'N' <= 10^5
-10^9 <= 'ARR[i]'<= 10^9
Time Limit : 1 sec

Solve now

Approaches

01 Approach

Approach: For this problem, we just need to form the `N/2` pairs of the numbers such that one number in the pair is just double the other.
So, we can greedily match every number with its double and go on till the last number. If it is impossible to match the current number, then we will return false.
We will start matching the numbers from the smallest number.

Algorithm :

Sort the given array 'ARR' using a custom comparator.
Make custom comparator function `compare` to compare two numbers based on their absolute value.
Initialize a map `frequency`.
Loop over the array 'ARR' and add one count to every occurrence of every array element.
Loop over the array again and add the following conditions:
If the value associated with the 'ARR[i]' as a key is zero, then continue.
If the value associated with the 2 * 'ARR[i]' as a key is zero, then return false.
Else decrease the count by one for the 'ARR[i]' and 2 * 'ARR[i]' as a key in the map.

Solve now