นับจำนวน 1 ใน Array หลัง N รอบการสลับค่าใน C

โจทย์

Array ขนาด N เริ่มต้นเป็น 0 ทั้งหมด ทำ N รอบ (Move):

• Move 1: สลับทุก Index (1,2,3...)
• Move 2: สลับ Index คู่ (2,4,6...)
• Move 3: สลับ Index หาร 3 ลงตัว (3,6,9...)
• ...
• Move i: สลับ Index ที่หาร i ลงตัว

นับจำนวน 1 ใน Array หลังจบ N รอบ

ข้อสังเกตสำคัญ (Mathematical Insight)

แต่ละ Index k จะถูกสลับ (Toggle) จำนวนครั้งเท่ากับ **จำนวนตัวหารของ k**

• ถ้าจำนวนตัวหารเป็น **คี่** → กลายเป็น 1
• ถ้าจำนวนตัวหารเป็น **คู่** → กลายเป็น 0

**จำนวนตัวหารเป็นคี่ ⇔ k เป็น Perfect Square (จำนวนกำลังสอง)**

เพราะตัวหารมักมาคู่กัน (d, k/d) ยกเว้น √k ที่คูณตัวเองได้

คำตอบ: จำนวน Perfect Squares ≤ N

Answer = floor(sqrt(N))

ตัวอย่าง N = 4

Initial: [0, 0, 0, 0]
Move 1: [1, 1, 1, 1]     (Toggle all)
Move 2: [1, 0, 1, 0]     (Toggle 2,4)
Move 3: [1, 0, 0, 0]     (Toggle 3)
Move 4: [1, 0, 0, 1]     (Toggle 4)
Final 1s: Index 1, 4 → 2 ones = floor(sqrt(4)) = 2

ตัวอย่าง N = 6

Perfect squares ≤ 6: 1, 4 → Count = 2

โปรแกรม C: Simulation (เข้าใจง่าย)

#include 

int countOnesSimulation(int n) {
    int arr[1000] = {0}; // Assume n <= 1000
    
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            arr[j - 1] ^= 1; // Toggle 0↔1
        }
    }
    
    int count = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] == 1) count++;
    
    return count;
}

int main() {
    int n;
    printf("Enter N: ");
    scanf("%d", &n);
    
    printf("Simulation: %d\n", countOnesSimulation(n));
    printf("Formula (sqrt): %d\n", (int)sqrt(n));
    
    return 0;
}

โปรแกรม C: Formula (Optimal)

#include 
#include 

int countOnesFormula(int n) {
    return (int)sqrt(n); // floor(sqrt(n))
}

int main() {
    int n;
    printf("Enter N: ");
    scanf("%d", &n);
    printf("Number of 1s: %d\n", countOnesFormula(n));
    return 0;
}

ผลลัพธ์:

Enter N: 100
Number of 1s: 10  (Perfect squares: 1,4,9,16,25,36,49,64,81,100)

Complexity Comparison

ข้อสรุป

นี่คือโจทย์คลาสสิก **"100 Doors Problem"** หรือ **"Locker Problem"** คำตอบคือ **จำนวน Perfect Squares ≤ N**