สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n มีร้านขายอุปกรณ์อิเล็กทรอนิกส์แห่งหนึ่งซึ่งมีการโจรกรรมเกิดขึ้นเมื่อคืนนี้ คีย์บอร์ดทั้งหมดที่มีอยู่ในร้านนั้นถูกเรียงลำดับจากน้อยไปมากจากจำนวนเต็ม 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 } ผลลัพธ์
2
