একটি সংখ্যার ডিজিটাল রুট (Digital Root) বের করতে হলে তার ডিজিটগুলোর যোগফল নিতে হয়; যদি যোগফল একক ডিজিট হয়, তবে সেটিই ডিজিটাল রুট। এই টিউটোরিয়ালে একটি সমস্যা আলোচনা করা হয়েছে যেখানে একটি সংখ্যা রেঞ্জ (range) এবং একটি পূর্ণসংখ্যা X দেওয়া আছে, এবং আমাদের গণনা করতে হবে রেঞ্জে কতগুলো সংখ্যার ডিজিটাল রুট X, যেখানে X একটি একক ডিজিট সংখ্যা। উদাহরণ −
ইনপুট: l = 13, r = 25, X = 4 আউটপুট: 2 ব্যাখ্যা: রেঞ্জ (13, 25)-এ ডিজিট সাম ৪ वाले সংখ্যা: ১৩ এবং ২২। ইনপুট: l = 11, r = 57 আউটপুট: 6
সহজ পদ্ধতিতে, l থেকে r পর্যন্ত সব সংখ্যা ট্রাভার্স করে চেক করা যাবে তার ডিজিট সাম X-এর সমান কিনা। কিন্তু এতে টাইম কমপ্লেক্সিটি O(N) হবে, যেখানে N হলো রেঞ্জে মোট সংখ্যা।
রেঞ্জে ডিজিটাল রুট X वाली সংখ্যা বের করতে, আমাদের প্রতিটি সংখ্যার ডিজিট সাম চেক করতে হবে যে সেটি K-এর সমান কিনা। ডিজিট সাম সবসময় num % ৯ (nine) এর সমান হয় এবং রিমেইন্ডার ০ হলে সেটি ৯ হয়। সুতরাং, যদি X = 9 হয়, তবে সেটিকে ০ मानতে হবে।
पूरा রেঞ্জকে ৯ দিয়ে ভাগ করে ৯-এর গ্রুপ (group) এ ভাগ করলে, প্রতিটি গ্রুপে ঠিক একটি সংখ্যা থাকবে যার মডুলো ৯ X-এর সমান। এরপর বাকি যেসব সংখ্যা গ্রুপে পড়েনি সেগুলো আলাদা করে চেক করব num % 9 = X কিনা।
উপরোক্ত পদ্ধতির C++ কোড
#include <bits/stdc++.h> #define ll long long int using namespace std; int main(){ int l = 13; int r = 25; int X = 4; if (X == 9) X = 0; // রেঞ্জে মোট সংখ্যা int total = r - l + 1; // ৯-এর সর্বোচ্চ গ্রুপে ভাগ int groups = total / 9; // N গ্রুপে Nটি সংখ্যা থাকবে যাদের মডুলো ৯ = X int result = groups; // বাকি সংখ্যা (left out) চেক int left_out = total % 9; // প্রতিটি বাকি সংখ্যা আলাদা চেক for (int i = r; i > r - left_out; i--) { int rem = i % 9; if (rem == X) result++; } cout << "Total Numbers in a Range( l, r ) with given Digital Root(X) are: " << result; return 0; }
Total Numbers in a Range( l, r ) with given Digital Root(X) are: 2
এই টিউটোরিয়ালে আমরা একটি সংখ্যা রেঞ্জ এবং ডিজিটাল রুট নিয়ে সমস্যা আলোচনা করেছি। আমাদের রেঞ্জে ডিজিটাল রুট X वाली সব সংখ্যা বের করতে হয়েছে। আমরা একটি সহজ পদ্ধতি এবং একটি দক্ষ পদ্ধতি দেখিয়েছি যেখানে সংখ্যাগুলো ৯-এর গ্রুপে ভাগ করা হয়েছে। প্রতিটি গ্রুপে একটি সংখ্যা থাকে যার ডিজিটাল রুট X। এই সমস্যার C++ প্রোগ্রামও দেওয়া আছে যা C, Java, Python ইত্যাদি ভাষায়ও করা যাবে। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।
