[Codility] Lesson3 - Time Complexity : Perm Missing Elem (c++)

Problem

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<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–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

How to solve

- 정보

N의 길이를 가진 서로 다른 정수 배열 A

정수의 범위: 1~N+1

 

 

- 구해야 하는것?

missing element 찾는 것!

 

- 예시

2, 3, 1, 5일 때 1부터 시작해서 missing element는 4!

 

- 풀이

A 배열 sort

A 배열에 원소가 없을 경우 1 return (주의!!!!!! 안써서 50% 나왔었음 ㅠㅠ)

마지막 원소까지 체크해야하기 때문에 for문 돌때 범위 i<=A.size() (주의!!!! for문 돌릴 때 범위 주의)

A[i] != i+1 이면, i+1이 누락된 것임! 따라서 i+1 return!

Solution(c++)

#include <bits/stdc++.h>

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)

    // sort
    if(A.size() == 0){
        return 1;
    }

    sort(A.begin(), A.end());

    for(int i=0; i<=A.size(); i++){
        if(A[i] != i+1){
            return i+1;
        }
    }
}

Test Result

처음 실패 result

성공 result

 

app.codility.com/demo/results/trainingHVTHP4-BS7/

Test results - Codility