algoadvance

Leetcode 1346. Check If N and Its Double Exist

Problem Statement

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

Clarifying Questions

  1. Input Size: What is the maximum size of the input array?
    • Let’s assume the size can be up to 10^4.
  2. Element Range: What are the possible values for the array elements?
    • The elements can vary widely, considering they can be positive, negative, or zero.
  3. Duplicates: Can the array have duplicate values?
    • Yes, the array can have duplicate values.

Strategy

To solve this problem efficiently, we can use a hash set. Here’s the step-by-step strategy:

  1. Iterate through each element in the array and store each element in a hash set.
  2. For each element x, check if 2 * x or x / 2 (only if x is even) exists in the set.
  3. If either condition is satisfied for any element, return true.
  4. If no such pairs are found after checking all elements, return false.

Code

#include <unordered_set>
#include <vector>
using namespace std;

bool checkIfExist(vector<int>& arr) {
    unordered_set<int> seen;
    for (int num : arr) {
        if (seen.count(2 * num) > 0 || (num % 2 == 0 && seen.count(num / 2) > 0)) {
            return true;
        }
        seen.insert(num);
    }
    return false;
}

Explanation

  1. Data Structure: We use an unordered_set seen to keep track of the elements we have encountered so far.
  2. Iteration and Condition Checks:
    • For each number in the array:
      • Check if 2 * num (double of the current number) already exists in the hash set.
      • If the current number is even, also check if num / 2 (half of the current number) exists in the hash set.
  3. Insertion: After checking the two conditions, insert the current number into the set.
  4. Return: If any of the conditions are met during the iteration, return true. If no conditions are met by the end of the loop, return false.

Time Complexity

This approach ensures that we efficiently check the conditions in linear time with respect to the size of the input array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI