ข้อความโจทย์
กำหนดอาร์เรย์จำนวนเต็มสองอาร์เรย์ even[] และ odd[] ซึ่งมีองค์ประกอบคู่และคี่ติดต่อกันตามลำดับ โดยมีองค์ประกอบหายไปหนึ่งตัวจากแต่ละอาร์เรย์ งานคือการหาองค์ประกอบที่หายไป
ตัวอย่าง
If even[] = {10, 8, 6, 16, 12} and odd[] = {3, 9, 13, 7, 11} then missing number from even array is 14 and from odd array is 5.
อัลกอริทึม
- เก็บค่าต่ำสุดและสูงสุดขององค์ประกอบคู่จากอาร์เรย์ even[] ในตัวแปร minEven และ maxEven
- ผลรวมของจำนวนคู่ N ตัวแรกคือ N * (N + 1) คำนวณผลรวมของจำนวนคู่จาก 2 ถึง minEven เรียกว่า sum1 และผลรวมของจำนวนคู่จาก 2 ถึง maxEven เรียกว่า sum2
- ผลรวมที่ต้องการของอาร์เรย์คู่จะเป็น reqSum = sum2 - sum1 + minEven การลบผลรวมของอาร์เรย์ even[] จาก reqSum นี้จะได้ตัวเลขคู่ที่หายไป
- เช่นเดียวกัน ตัวเลขคี่ที่หายไปก็สามารถหาได้เช่นกัน เนื่องจากเรารู้ว่าผลรวมของจำนวนคี่ N ตัวแรกคือ N²
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
void findMissingNums(int even[], int sizeEven, int odd[], int sizeOdd) {
int minEven = INT_MAX;
int maxEven = INT_MIN;
int minOdd = INT_MAX;
int maxOdd = INT_MIN;
int sumEvenArr = 0, sumOddArr = 0;
for (int i = 0; i < sizeEven; i++) {
minEven = min(minEven, even[i]);
maxEven = max(maxEven, even[i]);
sumEvenArr += even[i];
}
for (int i = 0; i < sizeOdd; i++) {
minOdd = min(minOdd, odd[i]);
maxOdd = max(maxOdd, odd[i]);
sumOddArr += odd[i];
}
int totalTerms = 0, reqSum = 0;
totalTerms = minEven / 2;
int evenSumMin = totalTerms * (totalTerms + 1);
totalTerms = maxEven / 2;
int evenSumMax = totalTerms * (totalTerms + 1);
reqSum = evenSumMax - evenSumMin + minEven;
cout << "Missing even number = " << reqSum - sumEvenArr << "\n";
totalTerms = (minOdd / 2) + 1;
int oddSumMin = totalTerms * totalTerms;
totalTerms = (maxOdd / 2) + 1;
int oddSumMax = totalTerms * totalTerms;
reqSum = oddSumMax - oddSumMin + minOdd;
cout << "Missing odd number = " << reqSum - sumOddArr << "\n";
}
int main() {
int even[] = {10, 8, 6, 16, 12};
int sizeEven = sizeof(even) / sizeof(even[0]);
int odd[] = {3, 9, 13, 7, 11};
int sizeOdd = sizeof(odd) / sizeof(odd[0]);
findMissingNums(even, sizeEven, odd, sizeOdd);
return 0;
}
ผลลัพธ์
Missing even number = 14 Missing odd number = 5
