หาค่ารากที่ 5 แบบ Floor ของตัวเลขใน C++

โจทย์

ได้รับจำนวน N ทางเราต้อง หาค่า Floor ของรากที่ 5 ของ N (ค่าจำนวนเต็มที่มากที่สุดที่ยกกำลัง 5 ไม่เกิน N)

ตัวอย่าง

Input: N = 325

Output: 3 (เพราะ 3^5 = 243, 4^5 = 1024 > 325)

แนวทางแก้ปัญหา

วิธี 1: Linear Search วนจาก 1 จนกว่า i^5 >= N แล้วคืน i-1

วิธี 2: Binary Search (เร็วกว่า) ค้นหาในช่วง [1, N] หาค่าที่มากที่สุดที่ i^5 ≤ N

โปรแกรมตัวอย่าง (Binary Search)

#include <iostream>
using namespace std;

int calcFifthRoot(int n) {
    if (n == 0 || n == 1) return n;
    int start = 1, end = n, root = 0;
    while (start <= end) {
        int a = (start + end) / 2;
        long long apow5 = 1LL * a * a * a * a * a;
        if (apow5 == n) return a;
        if (apow5 < n) { root = a; start = a + 1; }
        else end = a - 1;
    }
    return root;
}

int main() {
    int n = 250;
    cout << "The floor of fifth root of " << n << " is " << calcFifthRoot(n);
    return 0;
}

ผลลัพธ์

The floor of fifth root of 250 is 3