Số stepping number n chữ số C++

Stepping number: số mà hiệu giữa các chữ số liên tiếp là 1. Cho n (số chữ số), đếm tổng stepping number n chữ số.

Ví dụ: n=2 → 17. Từ 10 đến 99 có 17 stepping number.

Giải thuật

• Hàm isSteppingNumber(n): kiểm tra hiệu các cặp chữ số liên tiếp = 1
• lowest = 10^(n-1), highest = 10^n - 1
• Duyệt i từ lowest đến highest: nếu isSteppingNumber(i) thì count++
• Trả về count

Ví dụ minh họa

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

bool isSteppingNumber(int n) { 
    int previousDigit = -1; 
    while (n) { 
        int currentDigit = n % 10; 
        if (previousDigit != -1 && abs(previousDigit - currentDigit) != 1) return false; 
        previousDigit = currentDigit; 
        n /= 10; 
    } 
    return true; 
} 

int getSteppingNumbersCount(int n) { 
    int lowestNumber = pow(10, n - 1), highestNumber = pow(10, n) - 1; 
    int count = 0; 
    for (int i = lowestNumber; i <= highestNumber; i++) { 
        if (isSteppingNumber(i)) count += 1; 
    } 
    return count; 
} 

int main() { 
    int n = 3; 
    cout << getSteppingNumbersCount(n) << endl; 
    return 0; 
} 

Đầu ra

32