Số chữ số của số thứ N tạo từ 4 chữ số {1,2,3,4} trong C++

Xét dãy số chỉ dùng 4 chữ số {1,2,3,4}:

1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44, 111, ...

Nhiệm vụ: Tìm số chữ số của số thứ N trong dãy này.

Quan sát quy luật:

• 4 số có 1 chữ số (4¹)
• 16 số có 2 chữ số (4²)
• 64 số có 3 chữ số (4³)
• Tiếp tục theo lũy thừa của 4.

Thuật toán

• Khởi tạo result = 1, sum = 0.
• Với i = 4; lặp vô tận, i *= 4:
  • sum += i
  • Nếu sum >= N thì dừng.
  • result++
• Trả về result.

Triển khai C++

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

int getDigitsCount(int n) {
    int result = 1, sum = 0;
    for (int i = 4; ; i *= 4) {
        sum += i;
        if (sum >= n) break;
        result++;
    }
    return result;
}

int main() {
    int n = 57;
    cout << getDigitsCount(n) << endl; // Output: 3
    return 0;
}

Kết quả

3