[Arrays] Check If N and Its Double Exist

📋 This is my note-taking from what I learned in LeetCode!

Problem

Problem Link

Given an array arr of integers, check if there exist two indices i and j such that :

• i != j
• 0 <= i, j < arr.length
• arr[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
• -10^3 <= arr[i] <= 10^3

Hint #1:

Loop from i = 0 to arr.length, maintaining in a hashTable the array elements from [0, i - 1].

Hint #2:

On each step of the loop check if we have seen the element 2 * arr[i] so far or arr[i] / 2 was seen if arr[i] % 2 == 0.

Solution

Solution Link

Approach 1: Keeping track of elements seen so far

Iterating through the input array → Keeping track of elements seen so far in a hash table

For each element arr[i] in the array, we check if its double (2 * arr[i]) or half (arr[i] / 2) has been seen before.

If 2 * arr[i] or arr[i] / 2 is found in the hash table, we have found two indices i and j such that i != j, 0 <= i, j < arr.length, and arr[i] == 2 * arr[j] or arr[i] == arr[j] / 2. In this case, we return True.

If we have iterated through the entire array and have not found a matching pair of indices, we return False.

Algorithm:

1. Initialize an empty hash table “seen”.
2. Iterate through the input array arr, with index i from 0 to n-1, where n is the length of arr.
3. For each arr[i], check if 2 * arr[i] or arr[i] / 2 is in the seen hash table. If it is, return True.
4. Otherwise, add arr[i] to the seen hash table.
5. If we have iterated through the entire array and not found a match, return False.

def checkIfExist(arr: list[int]) -> bool:
    seen = {}
    for i in range(len(arr)):
        if (arr[i] * 2 in seen) or (arr[i] % 2 == 0 and arr[i] // 2 in seen):
            return True
        seen[arr[i]] = i
    return False

arr = [10, 2, 5, 3]
result = checkIfExist(arr)
print(result)

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array, since it involves iterating over the entire array once.
• Space Complexity: O(n), since the size of the dictionary (seen) used to store the elements seen so far in the array can grow up to the size of the input array.

---

Back to Top

See other articles in Category Arrays