หาจำนวนเต็มบวกตัวที่ N ที่มี Digital Root เป็น X ด้วย C++

ภาพรวมปัญหา

ได้รับ N และ X หาตัวเลขบวกตัวที่ N ที่มี Digital Root เท่ากับ X

Digital Root: ผลรวมหลักของตัวเลข ทำซ้ำจนเหลือ 1 หลัก

Digital Root(40) = 4+0 = 4
Digital Root(38) = 3+8=11 → 1+1=2

ตัวอย่าง

อินพุต

N = 5, X = 4

เอาต์พุต

40

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

วิธีที่ 1: Brute Force - O(N)

นับตั้งแต่ 1 ขึ้นไปจนกว่าจะเจอ N ตัวที่มี Digital Root = X

วิธีที่ 2: สูตรโดยตรง - O(1) ⭐

Digital Root ทำซ้ำทุก 9 ตัวเลข: 1,2,3,4,5,6,7,8,9, 1,2,3...

ตัวเลขที่มี Digital Root = X คือ: X, X+9, X+18, X+27, ...

สูตร: Nth number = (N-1) × 9 + X

โค้ดตัวอย่าง (สูตร O(1))

#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;
}

เอาต์พุต

12th positive number whose digital root is 4 is 103

สรุป

Digital Root มีรูปแบบซ้ำทุก 9 ตัว ใช้สูตรคำนวณตรงได้เลย ไม่ต้องวนลูป