【codility】Lesson 3: Time Complexity PermMissingElem

subject

Lesson 3: Time Complexity PermMissingElem
N個の異なる整数配列が渡されたとき、抜けている番号を返す問題。
例）
配列が、A = {2,3,1,5}であった場合は、 4を返す。

submit

1回でscore100にいけなかった。
・コーナーケースを考えることが必要
　・配列が空であった時のケース
　・一番最後の数字が抜けているケースなど

program

point:1~N+1までの和と、配列Aの中の要素の和を引いて求める
1～N+1までのすべての数字は必ず1回現れるので、1つ1つの数字を比較するのではなく、差分を見ることで足りない数字を導き出した。
最初は1つ1つ比較しようとしてたが、Lesson2での教訓から少し視点を変えて考えることができた。

permMissingElem.cpp

#include<iostream>
#include<vector>
using namespace std;

int solution(vector<int> &A) {
    int sum = 0;
    int totalSum = 0;
    int A_length = (int)A.size();
    if(!A.empty()){
        for (int i = 0; i < A_length; ++i) {
            sum = sum + A[i];
            totalSum += i + 1;
        }
        totalSum += A_length+1;
        return (totalSum - sum);
    }
    return 1;
}