Sponsored
Sponsored
This approach uses a Hash Set to store elements as we iterate through the array. For each element, we check if its double or half (only if it's even) exists in the set. This allows for efficient lookup and insertion operations.
Time Complexity: O(n), because we iterate through the array once and do constant time operations for each element.
Space Complexity: O(1), since the hash set size is fixed regardless of input size.
1def checkIfExist(arr):
2 seen = set()
3 for num in arr:
4 if 2 * num in seen or (num % 2 == 0 and num // 2 in seen):
5 return True
6 seen.add(num)
7 return FalseThe Python solution employs a set to track numbers that have been visited. For each number, we check if its double or its half (provided the number is even) is already in the set.
This approach involves sorting the array first. Once sorted, we can use two pointers to find if there exist indices i and j such that one element is twice the other. Sorting helps to systematically check this condition.
Time Complexity: O(n log n) for sorting, then O(n^2) for the two-pointer search.
Space Complexity: O(1) as it sorts in place.
1
This C code sorts the array and then uses a nested loop to check for any two elements where one is twice the other, leveraging the sorted order to avoid unnecessary comparisons.