Number, and it’s double.

Easy

0/40

Average time to solve is 15m

Contributed by

4 upvotes

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

False
True

Explanation Of Sample Input 1:

Test Case 1: In the given array, there are no two integers, ‘P’ and ‘Q’, such that P = 2*Q.

Test Case 2: ‘2’ is double of ‘1’. So for P = 2, Q = 1. P = 2*Q.

Sample Input 2:

2
6
10 12 5 20 0 11
3
2 2 2

Sample Output 2

True
False

Hint 1

Hint 2

Think of iterating through the array for every integer in ‘A’.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.
Return false if there exist no two integers such that one is double of another.

Time Complexity

O(N^2), where ‘N’ is the number of integers in the array.

For every element in ‘A’, we are iterating through the complete array. Therefore the time complexity is O(N^2).

Space Complexity

O(1)

No extra space is used. So the space complexity is O(1).

(100% EXP penalty)

Number, and it’s double.

Console