Last Updated: 20 Apr, 2021
Number, and it’s double.
Easy
Asked in company
Given an array of integers ‘A’. You need to find two integers, ‘P’ and ‘Q’ in ‘A’, such that P = 2*Q. (i.e., P is double of Q).
For Example:
If A = [2, 5, 7, 4, 9], then P = 2*Q can hold true for P = 4 and Q = 2. Which are at the 0-th index and 3rd index respectively.
Input Format:
The first line contains a single integer ‘T’, denoting the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the number of integers in the array.
The second line of each test case contains ‘N’ space-separated integers that make ‘A’.
Output Format:
For each test case, print “True”, if there exist two integers in the array as described in the problem statement. Otherwise, print “False”.
Print the output of each test case 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 <= A[i] <= 10^9
Where A[i] is the integer at index ‘i’.
Time limit: 1 sec
Approaches
The simple idea is that for every integer in ‘A’, traverse the complete array and check if there exists an integer that is double of it. If for any integer, it double exists, we will return true, otherwise false.
Below are the steps:
- Iterate through the array ‘A’ using a variable ‘i’ to check every element of ‘A’.
- Again iterate through ‘A’ using a variable ‘j’ to check if there exists an element that is double of ‘A[i]’.
- If ‘i’ is not equal to ‘j’ and ‘A[j]’ is double of ‘A[i]’, return true.
- Again iterate through ‘A’ using a variable ‘j’ to check if there exists an element that is double of ‘A[i]’.
- Return false if there exist no two integers such that one is double of another.
We can solve this problem by using a hash map. We will initialize a map 'M' that maps from integer to integer where key denotes the integer present in the array and value at that index denotes the number of times that integer occurs in the array.
Below are the steps:
- Initialize a hash map ‘M’ to store all the integers in the array ‘A’.
- Traverse through the array using a variable ‘i’.
- If 'A[i]' exists in 'M', increment its value by ‘1’; otherwise, insert 'A[i]' in the map.
- Now traverse through the array again using the variable ‘i’.
- If 'A[i]' is ‘0’, and ‘M[0]’ > 1, return true. It denotes that if there exist more than ‘1’ zeroes in the array, then return true.
- If 'M' contains a key = 2*'A[i]', return true.
- If 'A[i]' is even and 'M' contains a key = 'A[i]' / 2, return true. It denotes that if the current integer is even and there exists an integer whose value is half of 'A[i]', then return true.
- Return false if no such integers exist.