Check If N and Its Double Exist Leetcode Solution

Problem statement

In the problem ” Check If N and Its Double Exist” we are given an array of n elements. Array length is greater than or equal to two.

Our task is to check if there exists a pair in the array such that the first value is double the second value.

More formally we need to check if there exists i,j for which i <n,j<n and arr[i]=2*arr[j].

Example

arr = [7,1,14,11]

true

Explanation:

The output for this input is true because the question asks us to check if any value and its double exit in the given array, So 7 and 14 satisfies these criteria as 14 is double of 7.

Approach for Check If N and Its Double Exist Leetcode Solution

The first approach to solve this problem is the brute force approach. For each element in the array, we will traverse the complete array and check if it double exists. if we find an element satisfying this condition then we will return true, otherwise, we will return false at the end. The time complexity for this approach is O(n*n) because for every element of the array we are traversing the complete array.

We can solve this problem in a better time complexity using an unordered map or unordered set.

1. Traverse the array.
2. For every element in the array check if it’s double or its half already exists it the map.
3. If the condition is true simply return true else add that element into the map.
4. If array traversal is done and we didn’t find double of any element, then return false.

Implementation

C++ code for Check If N and Its Double Exist

#include <bits/stdc++.h> 
using namespace std; 
    bool checkIfExist(vector<int>& arr) {
      unordered_map<int,bool>mp;
        for(int i=0;i<arr.size();i++)
        {
            if(mp[arr[i]*2]==1||(mp[arr[i]/2]==1&&arr[i]%2==0))
                return true;
            mp[arr[i]]=1;
        }
        return false;
    }
int main() 
{ 
 vector<int> arr = {7,1,14,11}; 
 bool ans=checkIfExist(arr);
 cout <<boolalpha;
 cout<<ans<<endl;
 return 0;
}

true

Java code for Check If N and Its Double Exist

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static boolean checkIfExist(int[] arr) {
        Set<Integer> seen = new HashSet<>();   
        for (int i : arr) {
            if (seen.contains(2 * i) || (i % 2 == 0 && seen.contains(i / 2)))
                return true;
            seen.add(i);
        }
        return false;
    }
  public static void main(String[] args) {
        int [] arr = {7,1,14,11}; 
        boolean ans=checkIfExist(arr); 
        System.out.println(ans);
  }
}

true

Complexity Analysis of check If N and Its Double Exist Leetcode Solution

Time complexity

The time complexity of the above code is O(n) considering the average time complexity of searching and inserting in an unordered map as O(1).

Space complexity

The space complexity of the above code is O(n) because in the worst case we may need to store all the elements.

References