DEV Community

Cover image for 1346. Check If N and Its Double Exist
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

1346. Check If N and Its Double Exist

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
  • -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.

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

<?php
/**
 * @param Integer[] $arr
 * @return Boolean
 */
function checkIfExist($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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
?>
Enter fullscreen mode Exit fullscreen mode

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.

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:

Image of AssemblyAI tool

Challenge Submission: SpeechCraft - AI-Powered Speech Analysis for Better Communication

SpeechCraft is an advanced real-time speech analytics platform that transforms spoken words into actionable insights. Using cutting-edge AI technology from AssemblyAI, it provides instant transcription while analyzing multiple dimensions of speech performance.

Read full post

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay