1346. Check If N and Its Double Exist

Difficulty: Easy

Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

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³ <= arr[i] <= 10³

Hint:

1. Loop from i = 0 to arr.length, maintaining in a hashTable the array elements from [0, i - 1].
2. On each step of the loop check if we have seen the element 2 * arr[i] so far.
3. Also check if we have seen arr[i] / 2 in case arr[i] % 2 == 0.

Solution:

We can use a hash table (associative array) to track the elements we have already encountered while iterating through the array. The idea is to check for each element arr[i] if its double (i.e., 2 * arr[i]) or half (i.e., arr[i] / 2 if it's an even number) has already been encountered.

Here’s a step-by-step solution:

Plan:

1. Iterate through the array.
2. For each element arr[i], check if we have seen 2 * arr[i] or arr[i] / 2 (if arr[i] is even) in the hash table.
3. If any condition is satisfied, return true.
4. Otherwise, add arr[i] to the hash table and continue to the next element.
5. If no match is found by the end, return false.

Let's implement this solution in PHP: 1346. Check If N and Its Double Exist

  
  
  Explanation:




Hash Table: We use the $hashTable associative array to store the elements we've encountered so far.

First Condition: For each element arr[i], we check if arr[i] * 2 exists in the hash table.

Second Condition: If the element is even, we check if arr[i] / 2 exists in the hash table.

Adding to Hash Table: After checking, we add arr[i] to the hash table for future reference.

Return: If we find a match, we immediately return true. If no match is found after the loop, we return false.



  
  
  Time Complexity:



The time complexity is O(n), where n is the length of the array. This is because each element is processed once and checking or adding elements in the hash table takes constant time on average.



  
  
  Space Complexity:



The space complexity is O(n) due to the storage required for the hash table.


Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:


LinkedIn
GitHub



          

            
        
The above is the detailed content of Check If N and Its Double Exist. For more information, please follow other related articles on the PHP Chinese website!