[Codility] 3. Time Complexity | PermMissingElem

❓ Task

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

💡 Solution

class Solution {
    public int solution(int[] A) {
        long max = A.length+1; 
        long result = (1+max)*(max)/2;
        for(long a : A) result -= a;
        return (int) result;
    }
}

Carl Friedrich Gauss는 어렸을 때 이미 1부터 100까지의 수를 모두 더하는 문제를 아주 쉽게 풀었다고 하지요. 그 원리는 이렇습니다.

1 , 2 , 3 , … , 98, 99, 100
│ │ └-101-┘　│　│　
│ └---- 101-----┘　│
└------- 101----------┘
이런 방식으로 두 수를 더해 나가면 101이 50번 반복됩니다.
(1+100)*100/2

위와 같은 방식을 이용해서 1~(N+1) 사이의 수가 모두 존재하는 배열의 총 합을 구하는 식을 세웁니다.

(1 + (N+1)) * (N+1)/2

그리고 총합에서 임의의 수가 부재중인 배열 A의 총합을 빼주게 되면 부재중인 수만 남게 됩니다!

💬 Note

import java.util.*;

class Solution {
    public int solution(int[] A) {
        return (A.length+2)*(A.length+1)/2 - Arrays.stream(A).sum();
    }
}

처음에는 생각한 그대로 '완벽한 배열의 총합' - '부재중 배열의 총합'을 stream을 이용하여 계산하였습니다만... 퍼포먼스가 40% 밖에 안되었습니다.😓

시간복잡도를 감소시키기 위해 forEach를 통해 부재중 배열의 각 요소들을 하나씩 빼주도록 로직을 변경하였고 성능 상의 기준을 만족하게 되었습니다... 👏

stackoverflow에서 Arrays.stream().sum() 과 iteration for primitives를 비교하는 내용을 찾아 링크를 걸어둡니다.

🔗 [stackoverflow] Is Arrays.stream(array_name).sum() slower than iterative approach?