(Java) Check If N and Its Double Exist problem
JakeMIddleton
241
exploreFun With Arrays!

Brute force option

With this approach, simply check each element against all other elements, checking if there exists one that has double the value.
Time complexity: O(n2)
Space complexity: O(1)

public boolean checkIfExist(int[] arr) {
	if (arr.length <= 1) return false; //Cant exist if array is empty or only has one element
	
	for (int i=0; i<arr.length; i++){
		for (int j=0; j<arr.length; j++){
			if (j==i){
				continue;
			}
			if(arr[j] == 2*arr[i]){
				return true;
			}
		}
	}
	return false;
}

Hash table option

With a hash table, we can search for elements previously seen in linear time.
this means we can iterate through the elements, and check whether there has been an element that is either double or half of the current element.
Time complexity: O(n)
Space complexity: O(n)

import java.util.*; //Install package for Hashtables.
class Solution {
    public boolean checkIfExist(int[] arr) {
        //Cant exist if array is empty or only has one element
        if (arr.length <= 1) return false;
        
        Hashtable seen = new Hashtable();
        
        for (int i=0; i<arr.length; i++){
            if (seen.get(arr[i]*2) != null){
                return true;
            }
            if((arr[i]%2 == 0) && (seen.get(arr[i]/2) != null)){      //Since it is an array of integers, when we half an odd number it rounds down.
                return true;
            }
            seen.put(arr[i], true);
        }
        return false;
    }
}
Comments (2)