การนับจำนวนที่ผลต่างระหว่างตัวเลขและผลรวมของหลักไม่น้อยกว่า 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

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

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

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

• ใช้ num และ L เป็นตัวแปรแบบยาว

• ฟังก์ชัน Digit_sum(LL num) ใช้ตัวเลข num และส่งกลับผลรวมของตัวเลข

• นำผลรวมเริ่มต้นเป็นจำนวนทั้งหมด=0

• ใช้ while loop เพิ่มการเตือนความจำ num%10 เป็นยอดรวม และลด num ลง 10 ทำจนครบ num>0

• คืนค่าผลรวมเป็นผลรวมของตัวเลข

• ฟังก์ชัน Less_than_L(LL num, LL L) รับตัวเลข num และตัวเลข L และส่งกลับจำนวนตัวเลขดังกล่าว ซึ่งมีความแตกต่างระหว่างตัวเลขและผลรวมของหลักไม่น้อยกว่า L

• นับเริ่มต้นเป็น 0

• ใช้การค้นหาแบบไบนารีโดยใช้ while loop โดยที่ start=1 และ end=num

• คำนวณเลขกลางเป็น temp=(start+end)/2.

• หากความแตกต่างระหว่างอุณหภูมิและผลรวมของตัวเลขของอุณหภูมิไม่น้อยกว่า L ตัวเลขทั้งหมดที่มากกว่าอุณหภูมิจะเป็นไปตามเงื่อนไขเดียวกัน

• จำนวนตัวเลขดังกล่าวรวมทั้ง temp จะเป็น num-temp+1 เพิ่มสิ่งนี้เพื่อนับ และตั้งค่า end=temp-1.

• มิฉะนั้นให้ตั้งค่า start=temp+1.

• ในตอนท้ายของการค้นหาแบบไบนารีจะมีตัวเลขที่มีความแตกต่างระหว่างตัวเลขและจำนวนหลักไม่น้อยกว่า L

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

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