นับจำนวนกำลังสองและไม่ใช่กำลังสองก่อน N ใน C++

ภาพรวมปัญหา

ให้จำนวน N ต้องการนับจำนวนกำลังสอง (perfect squares) และไม่ใช่กำลังสอง ที่น้อยกว่าหรือเท่ากับ N

ตัวอย่าง

Input: N = 20

Output: Square: 4, Non-square: 16

คำอธิบาย: กำลังสอง: 1, 4, 9, 16

Input: N = 40

Output: Square: 6, Non-square: 34

คำอธิบาย: กำลังสอง: 1, 4, 9, 16, 25, 36

แนวทาง Naive (ตรวจสอบทุกตัว)

1. วนลูป i จาก 1 ถึง N
2. ถ้า floor(sqrt(i)) == ceil(sqrt(i)) หมายถึง i เป็นกำลังสอง
3. นับจำนวนกำลังสอง แล้ว Non-square = N - squares

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

#include <bits/stdc++.h>
#include <math.h>
using namespace std;

int squareNums(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (floor(sqrt(i)) == ceil(sqrt(i))) count++;
    }
    return count;
}

int main() {
    int N = 40;
    int squares = squareNums(N);
    cout << "Count of squares: " << squares;
    cout << " Count of non-squares: " << N - squares;
    return 0;
}

แนวทางที่มีประสิทธิภาพ (O(1))

จำนวนกำลังสอง ≤ N = ⌊√N⌋

เพราะกำลังสองคือ 1², 2², 3², ..., k² โดยที่ k² ≤ N < (k+1)² → k = ⌊√N⌋

โค้ดที่ปรับปรุงแล้ว

#include <bits/stdc++.h>
#include <math.h>
using namespace std;

int main() {
    int N = 40;
    int squares = floor(sqrt(N));
    cout << "Count of squares: " << squares;
    cout << " Count of non-squares: " << N - squares;
    return 0;
}

ผลลัพธ์

Count of squares: 6 Count of non-squares: 34

ความซับซ้อน

ข้อควรระวัง

• ใช้ floor(sqrt(N)) หรือ (int)sqrt(N) (การ cast จะ truncate ทศนิยม = floor)
• สำหรับ N ใหญ่มาก (ใกล้ 2⁶³) ใช้ integer sqrt เพื่อหลีกเลี่ยง floating point error