ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด N ประกอบด้วยค่าจำนวนเต็มตั้งแต่ 1 ถึง N และองค์ประกอบ x หนึ่งจากช่วงหายไป ในขณะที่องค์ประกอบ y ในอาร์เรย์เกิดขึ้นสองครั้ง ภารกิจของเราคือ หาตัวเลขที่ซ้ำและตัวเลขที่หายไปโดยใช้สองสมการ
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
arr[] = {1, 2 , 3, 3}
เอาต์พุต
missing = 4, double = 3
วิธีการแก้ปัญหา
วิธีหนึ่งในการแก้ปัญหาคือการใช้สองสมการสำหรับค่า x และ y แล้วแก้สมการเพื่อหาค่า x และ y
มาดูสมการและวิธีสร้างพวกมัน
ผลรวมขององค์ประกอบของอาร์เรย์ประกอบด้วยผลรวมของจำนวนธรรมชาติ N ตัวแรกพร้อมกับองค์ประกอบหนึ่งเพิ่มและอีกหนึ่งหายไป
arrSum = Sum(N) - x + y y - x = arrSum - sum(N)
นี่คือสมการ 1
ตอนนี้ มาหาผลรวมกำลังสอง คล้ายกัน
arrSumsq = sqSum(N) - x2 + y2 (y - x)*(y + x) = arrSumSq - sqSum(N)
ใช้สมการ 1
x + y = (arrSumSq - sqSum(N)) / (arrSum - sum(N))
บวกสมการทั้งสองเราได้
y = (arrSumSq - sqSum(N)) / (arrSum - sum(N)) + (arrSum - sum(N)) / 2
จากนั้นใช้ค่า y เราจะหา x โดยใช้
x = y - (arrSum - sum(N))
เรามีสูตรสำหรับ
sum(N) = n*(n-1)/2 sqSum(N) = n*(n+1)*(2n + 1)/ 6
arrSum คือผลรวมของทุกองค์ประกอบของอาร์เรย์
arrSumSq คือผลรวมของกำลังสองของทุกองค์ประกอบของอาร์เรย์
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include <iostream> using namespace std; void findExtraAndMissingVal(int arr[], int n){ int sumN = (n * (n + 1)) / 2; int sqSumN = (n * (n + 1) * (2 * n + 1)) / 6; int arrSum = 0, arrSqSum = 0, i; for (i = 0; i < n; i++) { arrSum += arr[i]; arrSqSum += (arr[i]* arr[i]); } int y = (((arrSqSum - sqSumN) / (arrSum - sumN)) + sumN - arrSum) / 2; int x = arrSum - sumN + y; cout<<"The missing value from the array is "<<x; cout<<"\nThe value that occurs twice in the array is "<<y; } int main() { int arr[] = { 1, 2, 2, 3, 4 }; int n = sizeof(arr)/sizeof(arr[0]); findExtraAndMissingVal(arr, n); return 0; }
เอาต์พุต
The missing value from the array is 2 The value that occurs twice in the array is 5
