สมมติว่าเราได้ให้อาร์เรย์ของจำนวนเต็มที่ไม่เรียงลำดับ ภารกิจคือการค้นหาจำนวนบวกที่ขาดหายไปซึ่งไม่มีอยู่ในอาร์เรย์ที่กำหนดในช่วง [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 ของแต่ละองค์ประกอบและดัชนีด้วย 'n' เราจะสามารถหาจำนวนผลลัพธ์เป็นตัวเลขเฉพาะที่ขาดหายไปจากอาร์เรย์
-
รับอินพุตขนาด N ของอาร์เรย์ที่มีองค์ประกอบอยู่ในช่วง [0 ถึง n]
-
ฟังก์ชันจำนวนเต็ม findMissingNumber(int arr[], int size) รับอาร์เรย์และขนาดเป็นอินพุตและส่งกลับตัวเลขที่หายไป
-
เอาล่ะ n เป็นตัวเลขที่ขาดหายไปเพื่อดำเนินการ XOR
-
วนซ้ำองค์ประกอบอาร์เรย์ทั้งหมดและดำเนินการ XOR กับองค์ประกอบอาร์เรย์แต่ละรายการและดัชนีที่เกี่ยวข้องกับตัวเลขที่ขาดหายไป เช่น 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 กับแต่ละองค์ประกอบของอาร์เรย์และดัชนีของอาร์เรย์ ก็จะพิมพ์ '5' ซึ่งหายไปจากอาร์เรย์
