최소 가능한 키보드 수를 찾는 C++ 프로그램 도난

<시간/>

n개의 요소가 있는 배열 A가 있다고 가정합니다. 어젯밤에 강도가 행해진 전자상가가 있었다. 상점 내부에 있는 모든 키보드는 정수 x에서 오름차순으로 번호가 매겨졌습니다. 예를 들어 x=4이고 상점에 3개의 키보드가 있는 경우 장치에는 인덱스 4, 5 및 6이 있습니다. x=10이고 그 중 7개가 있는 경우 키보드에는 인덱스 10, 11, 12, 13, 14, 15, 16. 강도 사건 이후 n개의 키보드만 남았다. 배열 A에 인덱스가 저장되어 있습니다. 도난당한 키보드의 가능한 최소 수를 찾아야 합니다.

따라서 입력이 A =[10, 13, 12, 8]과 같으면 출력은 2가 됩니다. x =8이면 도난당한 키보드의 최소 수는 2이기 때문입니다. 인덱스 9와 11이 있는 키보드는 도난당했습니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

sort the array A
n := size of A
return A[n - 1] - A[0] + 1 - n

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
      sort(A.begin(), A.end());
int n = A.size();
   return A[n - 1] - A[0] + 1 - n;
}
int main() {
   vector<int> A = { 10, 13, 12, 8 };
   cout << solve(A) << endl;
}

입력

{ 10, 13, 12, 8 }