Given an array arr of integers, check if there exist two indices i and j such that :
i != j0 <= i, j < arr.lengtharr[i] == 2 * arr[j]
Example 1:
Input: arr = [10,2,5,3] Output: true Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]
Example 2:
Input: arr = [3,1,7,11] Output: false Explanation: There is no i and j that satisfy the conditions.
Constraints:
2 <= arr.length <= 500-103 <= arr[i] <= 103This 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.
This C solution allocates a fixed-size boolean array to act as a hash set for values that have been seen. For each number, it checks if twice the number or half (if even) exists by using offset indexing for negative values.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Approach 1: Using a Hash Set | Time Complexity: O(n), because we iterate through the array once and do constant time operations for each element. |
| Approach 2: Sorting and Two Pointers | Time Complexity: O(n log n) for sorting, then O(n^2) for the two-pointer search. |
Check If N and Its Double Exist | Leetcode 1346 • Techdose • 2,184 views views
Watch 9 more video solutions →Practice Check If N and Its Double Exist with our built-in code editor and test cases.
Practice on FleetCode