C++ หาตัวเลขในช่วงที่มี Digital Root ตามที่กำหนด

Digital Root ของตัวเลขหาได้จากผลรวมของหลักๆ ถ้าผลรวมเป็นหลักเดียว นั่นคือ Digital Root ในบทช่วยสอนนี้ เราจะอภิบัติปัญหาที่เราได้รับช่วงของตัวเลขและจำนวนเต็ม X และต้องนับว่ามีตัวเลขกี่ตัวในช่วงที่มี Digital Root เป็น X โดย X เป็นตัวเลขหลักเดียว เช่น

Input: l = 13, r = 25, X = 4 Output: 2 Explanation: ตัวเลขในช่วง (13,25) ที่ผลรวมหลักเป็น 4 คือ 13 และ 22
Input: l = 11, r = 57 Output: 6

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

วิธีง่าย (Simple Approach)

ในวิธีง่าย เราสามารถวนลูปผ่านตัวเลขจาก l ถึง r และตรวจสอบว่าผลรวมเท่ากับ X หรือไม่ แต่จะสร้างความซับซ้อน O(N) โดย N คือจำนวนตัวเลขทั้งหมดในช่วง

วิธีมีประสิทธิภาพ (Efficient Approach)

เพื่อหาตัวเลขในช่วงที่มี Digital Root เป็น X เราต้องตรวจสอบผลรวมหลักของทุกตัวเลขในช่วงว่าเท่ากับ K และผลรวมหลักจะเท่ากับ num % 9 เสมอ และเป็น 9 ถ้าเศษเป็น 0 ดังนั้นถ้า X = 9 ให้เปลี่ยนเป็น 0

เพื่อนับจำนวน ให้แบ่งช่วงทั้งหมดเป็นกลุ่มละ 9 ตัว จะมีตัวเลขในแต่ละกลุ่มที่ modulo 9 เท่ากับ X อย่างแน่นอน 1 ตัว หลังจากนั้น ตรวจสอบตัวเลขที่เหลืออยู่นอกกลุ่ม ตรวจสอบแต่ละตัวแยกกันว่าตอบโจทย์ num % 9 = X หรือไม่

ตัวอย่าง

โค้ด C++ สำหรับวิธีการข้างต้น

#include <bits/stdc++.h> 
#define ll long long int 
using namespace std; 

int main(){ 
    int l = 13; 
    int r = 25; 
    int X = 4; 
    if (X == 9) X = 0; 
    int total = r - l + 1; 
    int groups = total / 9; 
    int result = groups; 
    int left_out = total % 9; 
    for (int i = r; i > r - left_out; i--) { 
        int rem = i % 9; 
        if (rem == X) result++; 
    } 
    cout << "Total Numbers in a Range( l, r ) with given Digital Root(X) are: " << result; 
    return 0; 
}

ผลลัพธ์

Total Numbers in a Range( l, r ) with given Digital Root(X) are: 2

สรุป

ในบทช่วยสอนนี้ เราอภิบัติปัญหาที่มีช่วงของตัวเลขและ Digital Root เราต้องหาตัวเลขทั้งหมดที่มี Digital Root เป็น X เราอภิบัติวิธีง่ายและวิธีมีประสิทธิภาพโดยการแบ่งตัวเลขเป็นกลุ่มละ 9 หลัก แต่ละกลุ่มมีตัวเลขหนึ่งตัวที่มี Digital Root เป็น X เรายังอภิบัติโปรแกรม C++ สำหรับปัญหานี้ ซึ่งสามารถทำได้กับภาษาอื่น เช่น C, Java, Python ฯลฯ หวังว่าจะเป็นประโยชน์