Tìm số dương thứ N có chữ số gốc (digital root) là X trong C++

Giới thiệu

Cho hai số nguyên N và X. Tìm số dương thứ N có chữ số gốc (digital root) bằng X.

Digital Root: Cộng các chữ số lặp lại cho đến khi được 1 chữ số. VD: 38 → 3+8=11 → 1+1=2.

Ví dụ minh họa

Đầu vào

N = 5, X = 4

Đầu ra

40

Phương pháp 1: Duyệt tuần tự - O(N)

Tính digital root cho từng số từ 1 trở lên, đếm đến khi tìm thấy số thứ N.

Chương trình minh họa

#include <iostream>
using namespace std;

int calcDigitalRoot(int num) {
    while (num >= 10) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        num = sum;
    }
    return num;
}

int calcNthDigitalRoot(int X, int N) {
    int count = 0;
    for (int i = 1; ; ++i) {
        if (calcDigitalRoot(i) == X) {
            ++count;
            if (count == N) return i;
        }
    }
    return -1;
}

int main() {
    int X = 4, N = 5;
    cout << N << "th positive number whose digital root is " << X << " is " << calcNthDigitalRoot(X, N);
    return 0;
}

Đầu ra

5th positive number whose digital root is 4 is 40

Phương pháp 2: Công thức trực tiếp - O(1)

Các số có digital root X tạo thành cấp số cộng: X, X+9, X+18, ... Công thức: Số thứ N = (N-1)×9 + X

Chương trình minh họa

#include <iostream>
using namespace std;

int calcNthDigitalRoot(int X, int N) {
    return (N - 1) * 9 + X;
}

int main() {
    int X = 4, N = 12;
    cout << N << "th positive number whose digital root is " << X << " is " << calcNthDigitalRoot(X, N);
    return 0;
}

Đầu ra

12th positive number whose digital root is 4 is 103