สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่ไม่ได้เรียงลำดับ งานคือหาตัวเลขบวกที่หายไปซึ่งไม่มีอยู่ในอาร์เรย์ที่กำหนดในช่วง [0 ถึง n] ตัวอย่างเช่น
ตัวอย่างอินพุต 1
N = 9, arr = [0, 2, 5, 9, 1, 7, 4, 3, 6]
เอาต์พุต
8
คำอธิบาย
ในอาร์เรย์ที่ไม่ได้เรียงลำดับ '8' คือจำนวนเต็มบวกเพียงตัวเดียวที่หายไป ดังนั้นเอาต์พุตคือ '8'
ตัวอย่างอินพุต 2
N = 1, arr = [0]
เอาต์พุต
1
คำอธิบาย
ในอาร์เรย์ที่กำหนด '1' คือจำนวนเต็มบวกเพียงตัวเดียวที่หายไป ดังนั้นเอาต์พุตคือ '1'
วิธีการแก้ปัญหา
มีหลายวิธีในการแก้ปัญหานี้ อย่างไรก็ตาม เราสามารถแก้ปัญหานี้ในเวลา O(n) แบบเส้นตรงและพื้นที่ O(1) แบบคงที่ได้
เนื่องจากเรารู้ว่าอาร์เรย์ของเรามีขนาด n และมีองค์ประกอบอยู่ในช่วง [0 ถึง n] อย่างแน่นอน ดังนั้นถ้าเราทำ XOR operation ของแต่ละองค์ประกอบและดัชนีของมันกับ 'n' เราสามารถหาตัวเลขผลลัพธ์เป็นตัวเลขที่ไม่ซ้ำกันที่หายไปจากอาร์เรย์ได้
- รับอินพุตขนาด N ของอาร์เรย์พร้อมองค์ประกอบในช่วง [0 ถึง n]
- ฟังก์ชัน integer findMissingNumber(int arr[], int size) รับอาร์เรย์และขนาดเป็นอินพุตและคืนค่าตัวเลขที่หายไป
- ให้ n เป็นตัวเลขที่หายไปเพื่อทำ XOR operation
- วนลูปผ่านองค์ประกอบอาร์เรย์ทั้งหมดและทำ XOR operation กับแต่ละองค์ประกอบอาร์เรย์และดัชนีของมันเกี่ยวกับตัวเลขที่หายไป คือ n
- ตอนนี้คืนค่าตัวเลขที่หายไป
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int findMissingNumber(int *arr, int size) {
int missing_no = size;
for (int i = 0; i < size; i++) {
missing_no ^= i ^ arr[i];
}
return missing_no;
}
int main() {
int n = 6;
int arr[n] = {0, 4, 2, 1, 6, 3};
cout << findMissingNumber(arr, n) << endl;
return 0;
}
ผลลัพธ์
ถ้าเราจะรันโค้ดด้านบน จะพิมพ์เอาต์พุตเป็น
5
ถ้าเราทำ XOR operation กับแต่ละองค์ประกอบของอาร์เรย์และดัชนีของมัน จะพิมพ์ '5' ซึ่งหายไปจากอาร์เรย์
