हमें एक संख्या 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 लेता है और उसके अंकों का योग वापस करता है।
- प्रारंभिक योग को total=0 लें।
- व्हाइल लूप का उपयोग करके, total में शेष num%10 जोड़ें और num को 10 से कम करें। ऐसा तब तक करें जब तक num>0।
- total को num के अंकों के योग के रूप में वापस करें।
- फ़ंक्शन Less_than_L(LL num, LL L) एक संख्या num और एक संख्या L लेता है और संख्या और उसके अंकों के योग का अंतर L से कम न होने वाली संख्याओं की गिनती वापस करता है
- प्रारंभिक गिनती 0 लें।
- व्हाइल लूप का उपयोग करके बाइनरी खोज लागू करें जहां start=1 और end=num।
- मध्य संख्या की गणना temp=(start+end)/2 के रूप में करें।
- यदि temp और temp के अंकों के योग का अंतर L से कम नहीं है तो temp से बड़ी सभी संख्याएं भी वही शर्त पूरी करेंगी।
- ऐसी संख्याओं की गिनती 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;
}
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
