Array Of Doubled Pair

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
0 upvote

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
8 6 3 4
6
1 3 4 5 2 5
Sample Output 1 :
true
false
Explanation Of Sample Input 1 :
For the first test case, it is possible to transform array like this [3, 6, 4, 8] which follows the rule 'ARR[2 * i + 1]' = 2 * 'ARR[2 * i]' for every 0 <= i < 'N' / 2.

For the second test case,  no arrangement of the array can follow the provided rule.
Sample Input 2 :
2
6
5 6 4 6 3 2
8
1 3 2 6 4 5 2 10
Sample Output 2 :
false
true
Hint

Try to match every number with its double valued number.

Approaches (1)
Greedy 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 : 

  1. Sort the given array 'ARR' using a custom comparator.
  2. Make custom comparator function `compare` to compare two numbers based on their absolute value.
  3. Initialize a map `frequency`.
  4. Loop over the array 'ARR' and add one count to every occurrence of every array element.
  5. 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.
Time Complexity

O(N * Log(N)), where 'N' is the length of the input array 'ARR'.

 

Since we are using hashmap for every key insertion and updation, it will take Log(N) complexity. Also, simultaneously we are looping over the whole array of size 'N' ; hence the overall time complexity will be O(N * Log(N)).

Space Complexity

O(N), where 'N' is the length of the input array 'ARR'.

 

In the worst-case Map can contain 'N' key-value pairs. Hence the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Array Of Doubled Pair
Full screen
Console