algoadvance

Given an array arr of integers, check if there exists two integers N and M such that N is twice M (i.e., N = 2 * M).

In other words, determine if there are two distinct indices i and j in the array such that arr[i] is double arr[j].

You need to return True if such elements exist, otherwise return False.

Clarifying Questions:

1. Q: Can the array contain negative numbers?
   • A: Yes, the array can contain negative numbers.
2. Q: Can the values in the array be zero?
   • A: Yes, zero can be part of the array, and zero is considered a special case where 0 = 2 * 0.
3. Q: What should be the return type?
   • A: The function should return a boolean value (True or False).

Strategy:

1. We can use a set to keep track of the elements we have seen so far as we iterate through the array.
2. For each element x in the array, we check if x/2 or 2*x exists in the set.
3. If either x/2 or 2*x is found in the set, we return True.
4. If none of the elements satisfy the condition, we return False at the end.

Code:

def checkIfExist(arr):
    seen = set()
    for x in arr:
        if x / 2 in seen or x * 2 in seen:
            return True
        seen.add(x)
    return False

Time Complexity:

• O(n): We iterate through the array once (O(n)) and each check and insertion in the set takes O(1) on average. Hence, the total time complexity is O(n) where n is the length of the array.

Explanation:

• We have a set called seen to track the elements we’ve come across.
• For each element x in the array:
  • We check if x / 2 or 2 * x is already in seen.
  • If either condition is true, we return True.
  • Otherwise, we add x to the set.
• If we finish the loop without returning True, it means no such pair exists, and we return False.

Example:

• For the input arr = [10, 2, 5, 3], the function should return True because 10 is twice 5.
• For the input arr = [7, 1, 14, 11], the function should return True because 14 is twice 7.
• For the input arr = [3, 1, 7, 11], the function should return False because no element is twice another in the array.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?