[Time Complexity] PermMissingElem

문제

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:

int solution(vector &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–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Solution

자꾸 틀려서 힘들었던 문제...
N+1까지의 합에서 A 벡터 요소들의 합을 빼면 되는 문제였다....
합을 long으로 받는 것이 중요.

  // you can use includes, for example:
  #include <algorithm>

  // you can write to stdout for debugging purposes, e.g.
  // cout << "this is a debug message" << endl;

  int solution(vector<int> &A) {
      // write your code in C++14 (g++ 6.2.0)
      long len = A.size();
      long sum = 0;

      long tot = (len+1) * (len+2) / 2;


      for(auto i : A){
          sum += i;
      }

      return (int)tot-sum;
  }

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

PermMissingElem coding task - Learn to Code - Codility