Check If N and Its Double Exist

EASY

Description

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³

Approaches

Checkout 3 different approaches to solve Check If N and Its Double Exist. Click on different approaches to view the approach and algorithm in detail.

Brute Force using Nested Loops

The most straightforward approach is to check every possible pair of elements in the array. We can use two nested loops to iterate through all pairs of indices (i, j) and verify if the condition arr[i] == 2 * arr[j] holds, ensuring that i and j are not the same.

Algorithm

Initialize two nested loops, with iterators i and j, both from 0 to arr.length - 1.
Inside the inner loop, check if the indices are different (i != j).
If the indices are different, check if the condition arr[i] == 2 * arr[j] is met.
If the condition is true, a valid pair has been found, so return true immediately.
If the loops complete without finding any such pair, it means no such pair exists. Return false.

This method involves a systematic check of all pairs. The outer loop selects an element arr[i], and the inner loop iterates through all other elements arr[j] to see if arr[j] is half of arr[i]. The algorithm is as follows:

class Solution {
    public boolean checkIfExist(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // The indices must be different
                if (i != j && arr[i] == 2 * arr[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the number of elements in the array. For each element, we iterate through the entire array again, leading to a quadratic number of comparisons.Space Complexity: O(1), as we only use a few variables to store indices and the array length, which does not depend on the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra memory, making it space-efficient.

Cons:

Highly inefficient for large arrays due to its quadratic time complexity.
Performs many redundant checks.

Code Solutions

Checking out 4 solutions in different languages for Check If N and Its Double Exist. Click on different languages to view the code.

class Solution {
public
  boolean checkIfExist(int[] arr) {
    Map<Integer, Integer> m = new HashMap<>();
    int n = arr.length;
    for (int i = 0; i < n; ++i) {
      m.put(arr[i], i);
    }
    for (int i = 0; i < n; ++i) {
      if (m.containsKey(arr[i] << 1) && m.get(arr[i] << 1) != i) {
        return true;
      }
    }
    return false;
  }
}

Video Solution

Watch the video walkthrough for Check If N and Its Double Exist

Algorithms:

Binary SearchSorting

Patterns:

Two Pointers

Data Structures:

ArrayHash Table