আমাদের একটি সংখ্যা d দেওয়া আছে যা ডিজিট সংখ্যা নির্দেশ করে। লক্ষ্য হলো সর্বোচ্চ d ডিজিট বিশিষ্ট এবং কমপক্ষে একটি শূন্য (০) ধারণকারী ধনাত্মক পূর্ণসংখ্যার সংখ্যা বের করা। অর্থাৎ ১ ডিজিট, ২ ডিজিট, ৩ ডিজিট... d ডিজিট পর্যন্ত সব সংখ্যা যাতে কমপক্ষে একটি ০ থাকে।
প্রথমে d ডিজিটের সংখ্যা যাতে কমপক্ষে একটি ০ থাকে তা বের করি। ধরি d=3। ৩ ডিজিটের সংখ্যা যেখানে কমপক্ষে একটি ০ থাকে, সম্ভাব্য উপায়গুলো:
এখানে d1 হতে পারে ১ থেকে ৯: ৯ পথ d2 হতে পারে ০-৯: ১০ পথ d3 হতে পারে ০-৯: ১০ পথ মোট সম্ভাব্য সংখ্যা: ৯ × ১০ × ১০ = ৯ × ১০² d ডিজিটের জন্য সংখ্যা: ৯ × ১০ᵈ⁻¹ d ডিজিটের জন্য শূন্য ছাড়া সংখ্যা: ৯ᵈ কমপক্ষে একটি শূন্য সহ d ডিজিটের সংখ্যা = ৯ × ১০ᵈ⁻¹ - ৯ᵈ = ৯ × (১০ᵈ⁻¹ - ৯ᵈ⁻¹)
উদাহরণ দিয়ে বুঝি
ইনপুট − d=4
আউটপুট − সর্বোচ্চ 'd' ডিজিট বিশিষ্ট শূন্য ধারণকারী ধনাত্মক পূর্ণসংখ্যার সংখ্যা − ২৬১৯
ব্যাখ্যা − x ডিজিটের কমপক্ষে একটি শূন্য সহ সংখ্যা −
১ ডিজিটের সংখ্যা: ০ ২ ডিজিটের সংখ্যা: ৯ ৩ ডিজিটের সংখ্যা: ১৭১ ৪ ডিজিটের সংখ্যা: ২৪৩৯ মোট = ৯ + ১৭১ + ২৪৩৯ = ২৬১৯
ইনপুট − d=1
আউটপুট − সর্বোচ্চ 'd' ডিজিট বিশিষ্ট শূন্য ধারণকারী ধনাত্মক পূর্ণসংখ্যার সংখ্যা − ০
ব্যাখ্যা − ১ থেকে ৯ পর্যন্ত কোনো সংখ্যায় শূন্য নেই।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি
আমরা দুটি পদ্ধতি ব্যবহার করব। প্রথমটি হলো সাদা লুপ ব্যবহার করে নেভ הפשט পদ্ধতি। ১ ডিজিট থেকে d ডিজিট পর্যন্ত ঘুরে উপরের ফর্মুলা দিয়ে সংখ্যা বের করে যোগ করা।
- ডিজিটের জন্য পূর্ণসংখ্যা
dনিন। total_count(int d)ফাংশনdডিজিটের কমপক্ষে একটি শূন্য সহ সংখ্যার কাউন্ট রিটার্ন করে।- সূত্র:
temp = 9 * (pow(10, d-1) - pow(9, d-1))দিয়ে গণনা করুন। tempরিটার্ন করুন।maximum_d(int d)ফাংশন সর্বোচ্চdডিজিট পর্যন্ত শূন্য সহ সংখ্যার মোট কাউন্ট রিটার্ন করে।- লুপ দিয়ে ১ থেকে
dপর্যন্ত প্রতিটি ডিজিটের জন্যtotal_count(i)কলে করুন এবংcount-এ যোগ করুন। - শেষে মোট কাউন্ট রিটার্ন করুন।
দক্ষ পদ্ধতি (Efficient Approach)
এই পদ্ধতিতে আমরা উপরের গণনার জিপি (GP) সিরিজ দেখে সরাসরি ফর্মুলা ব্যবহার করব।
সমাধান: ৯ × (10ᵈ⁻¹ - ৯ᵈ⁻¹) = ৯ × (10ᵈ - ১) - ৯ × (9ᵈ - ১) = ৯ × (10ⁱ - ১) - ৯ × (9ⁱ - ১) (১ ≤ i ≤ d) = GP¹ - GP² = ৯×(10ᵈ-১)/(১০-১) - ৯×(9ᵈ-১)/(৯-১) = (10ᵈ-১) - (৯/৮)×(9ᵈ-১)
- সর্বোচ্চ ডিজিট
dনিন। maximum_d(int d)ফাংশন সর্বোচ্চdডিজিট পর্যন্ত শূন্য সহ সংখ্যার কাউন্ট রিটার্ন করে।- উপরের ফর্মুলা দিয়ে
temp_1 = 9*((pow(10,d)-1)/9)গণনা করুন। temp_2 = 9*((pow(9,d)-1)/8)গণনা করুন।count = temp_1 - temp_2সেট করুন।countরিটার্ন করুন।
উদাহরণ (সাদা পদ্ধতি)
#include <bits/stdc++.h>
using namespace std;
int total_count(int d) {
int temp = 9 * (pow(10, d-1) - pow(9, d-1));
return temp;
}
int maximum_d(int d) {
int count = 0;
for (int i = 1; i <= d; i++) {
count = count + total_count(i);
}
return count;
}
int main() {
int d = 5;
cout << "Count of positive integers with 0 as a digit and maximum 'd' digits are: " << maximum_d(d) << endl;
return 0;
}
আউটপুট
Count of positive integers with 0 as a digit and maximum 'd' digits are: 33570
উদাহরণ (দক্ষ পদ্ধতি)
#include <bits/stdc++.h>
using namespace std;
int maximum_d(int d) {
int temp_1 = 9 * ((pow(10, d) - 1) / 9);
int temp_2 = 9 * ((pow(9, d) - 1) / 8);
int count = temp_1 - temp_2;
return count;
}
int main() {
int d = 4;
cout << "Count of positive integers with 0 as a digit and maximum 'd' digits are: " << maximum_d(d) << endl;
return 0;
}
আউটপুট
Count of positive integers with 0 as a digit and maximum 'd' digits are: 2619
