1346. Check If N and Its Double Exist

[mah-shamim]

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
• -103 <= arr[i] <= 103

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.

[mah-shamim]

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

<?php
function checkIfExist($arr) {
    $hashTable = array();

    foreach ($arr as $num) {
        // Check if double of the number exists in the hash table
        if (isset($hashTable[$num * 2])) {
            return true;
        }

        // Check if half of the number exists in the hash table (only if num is even)
        if ($num % 2 == 0 && isset($hashTable[$num / 2])) {
            return true;
        }

        // Add the current number to the hash table
        $hashTable[$num] = true;
    }

    return false;
}

// Example usage
$arr1 = [10, 2, 5, 3];
$arr2 = [3, 1, 7, 11];

echo checkIfExist($arr1) ? 'true' : 'false'; // Output: true
echo "\n";
echo checkIfExist($arr2) ? 'true' : 'false'; // Output: false
?>

Explanation:

1. Hash Table: We use the $hashTable associative array to store the elements we've encountered so far.
2. First Condition: For each element arr[i], we check if arr[i] * 2 exists in the hash table.
3. Second Condition: If the element is even, we check if arr[i] / 2 exists in the hash table.
4. Adding to Hash Table: After checking, we add arr[i] to the hash table for future reference.
5. 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.

[topugit]

Thanks to solve this problem efficiently

[mah-shamim]

Thanks