Java: Missing number in array

GeekforGeeks Practice

Missing number in array | Practice

0. Basic 문제

입력:

int T (테스트케이스 숫자)

int N (배열 크기) (배열은 1~N까지 정렬된 배열로 가정)

int[] A (ex. 1 2 3 5)

 

출력:

빠진 element

 

예제 입력 1)

2
5
1 2 3 5
10
1 2 3 4 5 6 7 8 10

예제 출력 1)

4
9

 

1. Java 8+ nextLine() -> int 배열로 변환

int[] arr = Arrays.stream(s.trim().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

 

2. 아이디어

하나의 요소가 빠진 배열의 크기를 구해서 (N)

((N + 1) * (N + 2) / 2) - (배열 총 합) = 빠진 숫자가 나온다.

int total = (arr.length + 1)*(arr.length + 2) / 2;

int current = Arrays.stream(arr).sum();

int missing = total - current;

 

ex)

int N = 5;

int [] A = {1, 2, 3, 5};

int total = (arr.length + 1)*(arr.length + 2) / 2;  // (5) * (6) / 2 = 15

int current = Arrays.stream(arr).sum();  // 총 합은 현재 11

System.out.println(total - current)  // 4

 

3. Java 소스

private static void missingNumber() {
    Scanner scan = new Scanner(System.in);
    int T = scan.nextInt();
    for (int i = 0; i < T; i++) {
        int N = scan.nextInt();
        scan.nextLine();  // nextInt() "\n" consume
        
        String s = scan.nextLine();
        int[] arr = Arrays.stream(s.trim().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        //System.out.println(Arrays.toString(arr));
        int total = (arr.length + 1)*(arr.length + 2) / 2;
        int current = Arrays.stream(arr).sum();

        System.out.println(total - current);
    }
}