Check If N and Its Double Exist - Practice Coding Problems

Check If N and Its Double Exist - Problem

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]

Return true if such indices exist, otherwise return false.

Input & Output

Example 1 — Basic Double Found

$ Input: arr = [10,2,5,3]

› Output: true

💡 Note: We can find 10 and 5 where 10 == 2 * 5, so there exists i=0 and j=2 such that arr[i] == 2 * arr[j]

Example 2 — No Double Exists

$ Input: arr = [3,1,7,11]

› Output: false

💡 Note: No element in the array is exactly double another element: 3≠2×1, 3≠2×7, 3≠2×11, and no other pairs work

Example 3 — Zero Edge Case

$ Input: arr = [0,0]

› Output: true

💡 Note: We have two zeros, and 0 == 2 * 0, so arr[0] == 2 * arr[1] with different indices i=0, j=1

Constraints

2 ≤ arr.length ≤ 500
-10³ ≤ arr[i] ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [10,2,5,3] - need to find double pairs

Check Relationships

For each element, check if 2×element or element÷2 exists

Found Match

10 and 5 satisfy: 10 == 2×5, return true

Key Takeaway

🎯 Key Insight: Use a hash set to check if 2×current or current÷2 already exists in one pass

Asked in

G Google 12 a Amazon 8 M Microsoft 6 Apple 4

The key insight is to check if for any element, either its double or half exists elsewhere in the array. The optimal hash set approach achieves this in O(n) time by storing seen elements and checking for 2×num or num÷2. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Optimization	O(n)	O(n)	Use a hash set to store seen numbers and check for doubles in one pass
Brute Force - Check All Pairs	O(n²)	O(1)	Compare every element with every other element to find the double relationship
Sort and Two Pointers	O(n log n)	O(n)	Sort the array first, then use two pointers to find the double relationship

Hash Set Optimization — Algorithm Steps

Create an empty hash set
For each element, check if 2×element or element÷2 exists in set
Add current element to set
Return true if match found, false otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Element

Check if 2×current or current÷2 exists in set

Add to Set

Add current element to seen set

Found Match

When we see 5, we find 2×5=10 already in set

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define HASH_SIZE 20000

struct HashNode {
    int value;
    struct HashNode* next;
};

struct HashNode* hashTable[HASH_SIZE];

int hashFunction(int key) {
    return abs(key) % HASH_SIZE;
}

bool contains(int key) {
    int hash = hashFunction(key);
    struct HashNode* node = hashTable[hash];
    while (node) {
        if (node->value == key) return true;
        node = node->next;
    }
    return false;
}

void insert(int key) {
    if (contains(key)) return;
    int hash = hashFunction(key);
    struct HashNode* newNode = malloc(sizeof(struct HashNode));
    newNode->value = key;
    newNode->next = hashTable[hash];
    hashTable[hash] = newNode;
}

bool solution(int* arr, int arrSize) {
    for (int i = 0; i < HASH_SIZE; i++) {
        hashTable[i] = NULL;
    }
    
    for (int i = 0; i < arrSize; i++) {
        int num = arr[i];
        // Check if double exists
        if (contains(2 * num)) {
            return true;
        }
        // Check if half exists (only for even numbers)
        if (num % 2 == 0 && contains(num / 2)) {
            return true;
        }
        insert(num);
    }
    return false;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int arr[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    bool result = solution(arr, size);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with O(1) hash set lookups and insertions

✓ Linear Growth

Space Complexity

O(n)

Hash set stores up to n elements in worst case

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler