หาตัวเลข Tidy ใกล้ที่สุดและน้อยกว่า N ใน C++

โจทย์

ให้จำนวน N ต้องการหาตัวเลข Tidy ที่ใกล้ที่สุดและน้อยกว่าหรือเท่ากับ N

Tidy Number = ตัวเลขที่หลักๆ เรียงจากน้อยไปมาก (Non-decreasing) เช่น 123, 112, 44999

ตัวอย่าง: N=45000 → Tidy ใกล้ที่สุดคือ 44999

วิธีแก้ปัญหา

สแกนจากหลังมาหน้า (Right to Left):

1. ถ้า digit[i] > digit[i+1] (ละเมิด Tidy property)
2. ลด digit[i] ลง 1
3. ตั้ง digit[i+1] ถึงท้ายให้เป็น 9 ทั้งหมด

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

string tidyNum(string number) {
    for (int i = number.length() - 2; i >= 0; i--) {
        if (number[i] > number[i + 1]) {
            number[i]--;
            for (int j = i + 1; j < number.length(); j++)
                number[j] = '9';
        }
    }
    return number;
}

int main() {
    string str = "45000";
    string num = tidyNum(str);
    cout << "The tidy number is: " << num;
}

ผลลัพธ์

The tidy number is: 44999