Jobs

Interviews

Discussions

Check If N and Its Double Exist #1631 Most Asked

Easy

Google

6 views

Topics:

Arrays

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³

Try coding it in LeetCode

Check If N and Its Double Exist #1631 Most Asked

Easy

Google

6 views

Topics:

Arrays

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³

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the integers in the array can take? Can I expect negative numbers, zeros, or large positive numbers?
What should I return if no such N and its double exist in the array? Should I return null, false, or throw an exception?
Is it possible for the input array to be empty or null? If so, what should I return?
If the array contains multiple pairs of N and its double, should I return only one pair or all of them?
If '0' exists in the array, is '0' considered its own double, and would [0, 0] be a valid solution?

Brute Force Solution

Approach

We need to see if, within a group of numbers, any number has its double also present in the group. The brute force approach is all about checking every possible pairing of numbers to see if the condition is met.

Here's how the algorithm would work step-by-step:

Take the first number in the group.
Look at every other number in the group to see if any of them are exactly twice the first number.
If you find a number that's twice the first number, the job is done! We know the condition is met.
If you go through all the other numbers and none of them are twice the first number, then move on to the second number in the original group.
Repeat the process: check every other number to see if it's twice the second number.
Keep doing this until you either find a match or you've checked every number in the group.

Code Implementation

def check_if_n_and_double_exist(number_list):
    list_length = len(number_list)

    for first_number_index in range(list_length):
        first_number = number_list[first_number_index]

        # Iterate through list, comparing to first_number
        for second_number_index in range(list_length):
            # Skip checking if number is same as first
            if first_number_index == second_number_index:
                continue

            second_number = number_list[second_number_index]

            # Check if second number is double the first
            if second_number == 2 * first_number:
                return True

    # If no double is found, return False
    return False

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array. For each element, it iterates through the rest of the array to check if any element is its double. This inner loop also runs up to n times. Therefore, the number of operations grows proportionally to n multiplied by n, resulting in approximately n * n operations which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force approach only uses a few constant space variables for indices to iterate through the input array. No additional data structures like lists, maps, or sets are created to store intermediate results or track visited elements. The space used does not depend on the size of the input array, denoted as N. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The most efficient way to solve this problem is to check for a number's double quickly. We can do this by first storing all the numbers we see and then checking for each number if its double is already stored.

Here's how the algorithm would work step-by-step:

Go through the list of numbers one by one.
For each number, check if its double is present somewhere else in the list.
To make this check fast, keep track of all the numbers you've seen so far in a special storage place like a set.
Before adding a new number to this storage, check if its double is already in the storage.
Also, before adding a number, check if half of it (if it's an even number) is in the storage. This handles cases like 4 being the double of 2.
If you find a number and its double at any point, you know the answer is 'yes'.
If you go through all the numbers and don't find a number and its double, the answer is 'no'.

Code Implementation

def check_if_double_exists(arr):
    seen_numbers = set()

    for number in arr:
        # Before adding, check if double is already present
        if number * 2 in seen_numbers:
            return True

        # Before adding, check if half exists for even numbers
        if number % 2 == 0 and number // 2 in seen_numbers:
            return True

        seen_numbers.add(number)

    # If no double is found, return False
    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once. Inside the loop, the primary operations are checking for the presence of an element's double and half within a set. Set lookups (checking if an element exists) take O(1) time on average. Therefore, the dominant factor is the single iteration through the array, resulting in a time complexity of O(n).

Space Complexity

O(N) – The provided solution utilizes a set to store the numbers encountered while iterating through the input array. In the worst-case scenario, where no number and its double are found, the set will store all N elements of the input array. Therefore, the auxiliary space used is proportional to the size of the input array. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately as no double can exist.
Array with only one element	Return false because a number and its double require at least two elements.
Array containing only zeros	Handle the case where zero's double (zero) exists by checking for its presence and handling index issues carefully.
Array with large positive and negative numbers that could lead to integer overflow when doubled.	Consider using a language with automatic overflow handling or using a data type that can hold larger values to prevent overflow during multiplication.
Array with duplicate elements other than zero.	The hash set or map approach inherently handles duplicates by overwriting entries.
Array with no number and its double present	Return false after iterating through the entire array if no double is found.
Large input array causing memory constraints.	Optimize space usage by considering in-place modifications (if allowed) or alternative data structures.
Array contains only negative numbers	The algorithm should correctly identify doubled negative numbers.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the integers in the array can take? Can I expect negative numbers, zeros, or large positive numbers?
What should I return if no such N and its double exist in the array? Should I return null, false, or throw an exception?
Is it possible for the input array to be empty or null? If so, what should I return?
If the array contains multiple pairs of N and its double, should I return only one pair or all of them?
If '0' exists in the array, is '0' considered its own double, and would [0, 0] be a valid solution?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the group.
Look at every other number in the group to see if any of them are exactly twice the first number.
If you find a number that's twice the first number, the job is done! We know the condition is met.
If you go through all the other numbers and none of them are twice the first number, then move on to the second number in the original group.
Repeat the process: check every other number to see if it's twice the second number.
Keep doing this until you either find a match or you've checked every number in the group.

Code Implementation

def check_if_n_and_double_exist(number_list):
    list_length = len(number_list)

    for first_number_index in range(list_length):
        first_number = number_list[first_number_index]

        # Iterate through list, comparing to first_number
        for second_number_index in range(list_length):
            # Skip checking if number is same as first
            if first_number_index == second_number_index:
                continue

            second_number = number_list[second_number_index]

            # Check if second number is double the first
            if second_number == 2 * first_number:
                return True

    # If no double is found, return False
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the list of numbers one by one.
For each number, check if its double is present somewhere else in the list.
To make this check fast, keep track of all the numbers you've seen so far in a special storage place like a set.
Before adding a new number to this storage, check if its double is already in the storage.
Also, before adding a number, check if half of it (if it's an even number) is in the storage. This handles cases like 4 being the double of 2.
If you find a number and its double at any point, you know the answer is 'yes'.
If you go through all the numbers and don't find a number and its double, the answer is 'no'.

Code Implementation

def check_if_double_exists(arr):
    seen_numbers = set()

    for number in arr:
        # Before adding, check if double is already present
        if number * 2 in seen_numbers:
            return True

        # Before adding, check if half exists for even numbers
        if number % 2 == 0 and number // 2 in seen_numbers:
            return True

        seen_numbers.add(number)

    # If no double is found, return False
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately as no double can exist.
Array with only one element	Return false because a number and its double require at least two elements.
Array containing only zeros	Handle the case where zero's double (zero) exists by checking for its presence and handling index issues carefully.
Array with large positive and negative numbers that could lead to integer overflow when doubled.	Consider using a language with automatic overflow handling or using a data type that can hold larger values to prevent overflow during multiplication.
Array with duplicate elements other than zero.	The hash set or map approach inherently handles duplicates by overwriting entries.
Array with no number and its double present	Return false after iterating through the entire array if no double is found.
Large input array causing memory constraints.	Optimize space usage by considering in-place modifications (if allowed) or alternative data structures.
Array contains only negative numbers	The algorithm should correctly identify doubled negative numbers.