সংখ্যা এবং এর অঙ্কগুলোর যোগফলের পার্থক্য L-এর চেয়ে কম না হলে সংখ্যা গণনা (C++ প্রোগ্রাম)

আমাদের একটি সংখ্যা N এবং অন্য একটি সংখ্যা L দেওয়া আছে। লক্ষ্য হল ১ থেকে N পর্যন্ত এتا সংখ্যা বের করা যাদের নিজের সংখ্যা এবং তার অঙ্কগুলোর যোগফলের পার্থক্য L-এর চেয়ে কম নয়।

যদি N=23, L=10 হয়, তবে এমন সংখ্যার গণনা হবে ৪।

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-(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 নেয় এবং এর অঙ্কগুলোর যোগফল ফেরত দেয়।
আরম্ভিক যোগফল total=0 নিন।
while লুপ ব্যবহার করে num%10 বাকি total-এ যোগ করুন এবং num কে ১০ দিয়ে ভাগ করুন। num>0 পর্যন্ত এটা চালান।
total কে num-এর অঙ্কগুলোর যোগফল হিসেবে ফেরত দিন।
Less_than_L(LL num, LL L) ফাংশন একটি সংখ্যা num এবং একটি সংখ্যা L নেয় এবং সংখ্যা এবং এর অঙ্কগুলোর যোগফলের পার্থক্য L-এর চেয়ে কম না হলে সংখ্যা গণনা ফেরত দেয়।
আরম্ভিক গণনা ০ নিন।
বাইনারি সার্চ বাস্তবায়ন করুন while লুপ দিয়ে যেখানে start=1 এবং end=num।
মাঝপথের সংখ্যা হিসাব করুন temp=(start+end)/2।
যদি temp এবং এর অঙ্কগুলোর যোগফলের পার্থক্য L-এর চেয়ে কম নয়, তবে temp-এর চেয়ে বড় সব সংখ্যাও একই শর্ত পূরণ করবে।
তেমন সংখ্যাগুলোর গণনা temp সহ হবে num-temp+1। এটিকে count-এ যোগ করুন। এবং end=temp-1 সেট করুন।
অন্যথায় start=temp+1 সেট করুন।
বাইনারি সার্চ শেষে count-এ পার্থক্য L-এর চেয়ে কম নয় এমন সংখ্যাগুলো থাকবে।
ফলাফল হিসেবে count ফেরত দিন।

C++ প্রোগ্রাম উদাহরণ

#include 
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