Check If N and Its Double Exist

문제

전제
정수형 배열이 주어질때 두 정수 N과 M이 존재하는지 체크해라 N은 M의 두배 이다.(N = 2 * M )

두 인덱스 i와 j를 체크해야한다.

i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]

예제1

입력: arr = [10,2,5,3]
출력: true
설명 : N = 10은 M = 5의 두 배이다.즉, 10 = 2 * 5.

예제2

입력: arr = [7,1,14,11]
출력: true
설명 : N = 14는 M = 7의 두 배이다.즉, 14 = 2 * 7.

예제3

입력: arr = [3,1,7,11]
출력: false
설명 : 이 경우는 N과 M이 존재하지 않는다, N = 2 * M이기 때문이다.

제약 조건

2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3

---

Solution

class Solution {
     public boolean checkIfExist(int[] arr) {
	  
		for(int i = 0; i < arr.length; i++) {
			for(int j = i + 1; j < arr.length; j++) {
				
            	if((arr[j] == arr[i] * 2) || (arr[i] == arr[j] * 2)) {
					return true;
				}
                
			}
		}
        
		return false;
	}
}

인덱스 i와 j를 사용해 각 인덱스 요소가 두 배이면 true를 아니라면 false를 리턴해준다.

아래는 가장 빠른 코드이다.

class Solution {
    public boolean checkIfExist(int[] arr) {
        boolean[] hold = new boolean[4001];
        
        for(int n : arr) {
            if((n%2==0 && hold[(n/2)+2000]==true) || hold[(n*2)+2000]==true) 
                return true;
            hold[n+2000] = true;
        }
        
        return false;
    }
}

제약 조건 -10^3 <= arr[i] <= 10^3에서 음수를 제거하기 위해 boolean배열의 길이를 4001로 설정해주었다.
위 조건만 생각해봤을때 arr[i]는 -1000 ~ 1000이므로 음수를 제거하려면 arr[i]+1000을 하면 될 것 같다.
그렇게 되면 arr[i]+1000 = 0 ~ 2000으로 boolean의 크기는 2001이면 충분할 것 같지만
코드의 조건 중 arr[i]에 요소에 2를 곱해야 하므로 arr[i]가 -1000이면 arr[i]2조건이 존재하므로 -2000을 양수로 변환해줘야 한다.
따라서 arr[i] 2의 범위는 -2000 ~ 2000이 되고 음수를 양수로 변환 할 경우 2000을 더해주어야 하므로 0 ~ 4000이 되기 때문에 boolean을 4001로 설정해준다.
n의 값을 조회 할 때 마다 n+2000은 true가 되고 즉,
arr[1] = -1000일때 1000의 값을 true로 저장하고
만약 arr[2]가 -500이라면 hold[(n*2)+2000]==true 즉, hold[(-500*2)+2000] == true
위 조건에 부합해 true를 리턴 할 것이다.

HashTable을 활용한 방법도 있다.

import java.util.Hashtable;

class Solution {
    public boolean checkIfExist(int[] arr) {
		Hashtable<Integer, Integer> bucket= new Hashtable<>();
		
			for(int i = 0; i < arr.length; i++) {
						if(bucket.containsValue(arr[i]*2) 
                        || (arr[i] % 2 == 0 && bucket.containsValue(arr[i]/2))){
							return true;
						}
					bucket.put(i,arr[i]);
				}
                
       return false;
    }
}