หาตัวเลขบวกที่หายไปจากอาร์เรย์ Unsorted ใน Java (Missing Positive Number)

กำหนดให้มีอาร์เรย์ของจำนวนเต็มที่ไม่ได้เรียงลำดับ (unsorted) ขนาด N มีค่าอยู่ในช่วง [0, N] โดยมีตัวเลขเพียงตัวเดียวที่หายไป งานคือหาตัวเลขที่หายไปนั้น

ตัวอย่าง Input-1

N = 9
arr = [0, 2, 5, 9, 1, 7, 4, 3, 6]

Output

8

ตัวอย่าง Input-2

N = 1
arr = [0]

Output

1

แนวทางแก้ปัญหา: ใช้ XOR Operation (Time: O(n), Space: O(1))

คุณสมบัติของ XOR:

• a ^ a = 0
• a ^ 0 = a
• a ^ b ^ a = b (คำสั่ง XOR สลับที่ได้)

เนื่องจากอาร์เรย์มีขนาด N และมีค่าครอบคลุม [0, N] ทั้งหมด ยกเว้นตัวเดียว เราสามารถ XOR ทุกค่าในอาร์เรย์รวมกับดัชนี (index) และ N เอง จะได้ตัวเลขที่หายไป

หลักการ

missing = N
for i = 0 to N-1:
    missing ^= i ^ arr[i]
return missing

ค่าทุกค่าที่ปรากฏครบคู่จะถูก XOR กันหายไป เหลือเพียงค่าที่หายไป

ตัวอย่างโค้ด

public class Solution {
    public static int findMissingNumber(int[] arr, int size) {
        int missingNo = size; // เริ่มต้นด้วย N

        for (int i = 0; i < size; i++) {
            missingNo ^= i ^ arr[i];
        }
        return missingNo;
    }

    public static void main(String[] args) {
        int[] arr = {0, 4, 2, 1, 6, 3}; // ขนาด 6 ควรมีค่า 0-6
        int n = arr.length;
        int missing = findMissingNumber(arr, n);
        System.out.println("Missing number: " + missing);
    }
}

ผลลัพธ์

Missing number: 5

คำอธิบาย: ในอาร์เรย์ {0,4,2,1,6,3} ตัวเลข 5 หายไป

วิธีอื่นๆ

ข้อควรระวัง

• วิธี XOR ใช้ได้ก็ต่อเมื่อมีตัวเลขหายไป เพียงตัวเดียว และค่าอยู่ในช่วง [0, N] ทุกค่าไม่ซ้ำ
• หากอาจมีค่าซ้ำหรือข้อน้อยกว่า N ให้ใช้ HashSet แทน