Kiểm tra số có phải lũy thừa của k bằng phương pháp đổi cơ số trong C++

Cho một số và giá trị k. Kiểm tra xem số đó có phải là lũy thừa của k hay không bằng phương pháp đổi cơ số. Ví dụ số 27, k = 3. Khi đổi cơ số 3, 27 thành 1000₃. Nếu sau khi đổi cơ số chỉ có một chữ số 1 và các chữ số còn lại là 0 thì số đó là lũy thừa của k.

Thuật toán:

• Đặt flag = false.
• Khi number > 0:
  • Lấy digit = number % k.
  • Nếu digit > 1 → trả về false.
  • Nếu digit == 1: nếu flag đã true → false, ngược lại đặt flag = true.
  • number /= k.
• Trả về true.

Ví dụ

#include <iostream>
#include <cmath>
using namespace std;

bool isPowerOfK(int num, int k) {
    bool flag = false;
    while (num > 0) {
        int digit = num % k;
        if (digit > 1)
            return false;
        if (digit == 1) {
            if (flag)
                return false;
            flag = true;
        }
        num /= k;
    }
    return true;
}

int main() {
    int number = 27, K = 3;
    if(isPowerOfK(number, K)){
        cout << number << " is power of " << K;
    } else {
        cout << number << " is not power of " << K;
    }
}

Kết quả

27 is power of 3