จำนวนตัวเลขที่ผลต่างระหว่างตัวเลขและผลรวมหลักไม่ต่ำกว่า L ใน C++

เราได้รับตัวเลข N และอีกตัวเลขหนึ่ง L เป้าหมายคือหาตัวเลขระหว่าง 1 ถึง N ที่มีผลต่างระหว่างตัวเลขเองและผลรวมหลักของมัน ไม่ต่ำกว่า L

ถ้า N=23, L=10 จำนวนตัวเลขแบบนี้จะเป็น 4

23-(2+3)=18, 22-(2+2)=18, 21-(2+1)=18, 20-(2+0)=18

ตัวเลขทั้งหมดข้างต้นตรงตามเงื่อนไข

แต่ 19-(1+9)=9 ซึ่งน้อยกว่า L คล้ายกัน 18,17….1

ตัวอย่าง

อินพุต - N=30 L=19

เอาต์พุต - จำนวนตัวเลขที่ผลต่างระหว่างตัวเลขและผลรวมหลักไม่ต่ำกว่า L คือ - 1

คำอธิบาย - มีแค่ 30 ที่ตรงตามเงื่อนไข 30-(3+0)=27 > 19

อินพุต - N=123330 L=5466

เอาต์พุต - จำนวนตัวเลขที่ผลต่างระหว่างตัวเลขและผลรวมหลักไม่ต่ำกว่า L คือ - 6841

แนวทางที่ใช้ในโปรแกรมด้านล่าง

ใช้ Binary Search เราจะหาตัวเลขแรกที่ตรงตามเงื่อนไข ถ้าตัวเลขนั้นคือ num แล้วเงื่อนไขจะเป็นจริงสำหรับ num+1 และต่อไป

ถ้าค่า mid ปัจจุบันตรงตามเงื่อนไข ตัวเลขทั้งหมดระหว่าง mid และ end ก็จะตรงตามเงื่อนไขเดียวกัน ดังนั้นเราสามารถบวก end-mid+1 เข้า count ได้โดยตรง

• รับ num และ L เป็นตัวแปร long
• ฟังก์ชัน Digit_sum(LL num) รับตัวเลข num คืนค่าผลรวมหลักของมัน
• ตั้งค่า sum เริ่มต้นเป็น total=0
• ใช้ลูป while บวกเศษ num%10 เข้า total และลด num ลง 10 ทำซ้ำจนกว่า num>0
• คืนค่า total เป็นผลรวมหลักของ num
• ฟังก์ชัน Less_than_L(LL num, LL L) รับตัวเลข num และตัวเลข L คืนค่าจำนวนตัวเลขที่ผลต่างระหว่างตัวเลขและผลรวมหลักไม่ต่ำกว่า L
• ตั้งค่า count เริ่มต้นเป็น 0
• นำ Binary Search ไปใช้ด้วยลูป while โดย start=1 และ end=num
• คำนวณตัวเลขกลางเป็น temp=(start+end)/2
• ถ้าผลต่างระหว่าง temp และผลรวมหลักของ temp ไม่ต่ำกว่า L แล้วตัวเลขทั้งหมดที่มากกว่า temp ก็จะตรงตามเงื่อนไขเดียวกัน
• จำนวนตัวเลขแบบนั้นรวม temp จะเป็น num-temp+1 บวกเข้า count และตั้ง end=temp-1
• มิฉะนั้น ตั้ง start=temp+1
• ที่สิ้นสุดของ binary search count จะมีตัวเลขที่มีผลต่างระหว่างพวกเขาและผลรวมหลักไม่ต่ำกว่า L
• คืนค่า count เป็นผลลัพธ์

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

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

int Digit_sum(LL num){ 
    LL total = 0; 
    while (num > 0){ 
        total += num % 10; 
        num = num/10; 
    } 
    return total; 
} 

LL Less_than_L(LL num, LL L){ 
    LL count = 0; 
    LL start = 1; 
    LL end = num; 
    while (start <= end){ 
        LL temp = (end + start) / 2; 
        LL temp_2 = temp - Digit_sum(temp); 
        if (temp_2 >= L){ 
            count = num - temp + 1; 
            end = temp - 1; 
        } 
        else{ 
            start = temp + 1; 
        } 
    } 
    return count; 
} 

int main(){ 
    LL num = 234516; 
    LL L = 235; 
    cout << "Count of Numbers such that difference between the number and sum of its digits not less than L are: " << Less_than_L(num, L); 
    return 0; 
}

เอาต์พุต

Count of Numbers such that difference between the number and sum of its digits not less than L are: 234267