দুটি নম্বর start এবং end রেঞ্জ ভেরিয়েবল হিসেবে দেওয়া আছে। লক্ষ্য হল রেঞ্জ [start, end]-এ থাকা যেসব নম্বরের ইভেন পজিশনের ডিজিট সম এবং অড পজিশনের ডিজিট সমের পার্থক্য একটি প্রাইম নম্বর, তাদের সংখ্যা বের করা।
অর্থাৎ (ইভেন পজিশনের ডিজিট সম) - (অড পজিশনের ডিজিট সম) = একটি প্রাইম নম্বর।
উদাহরণ দিয়ে বোঝা যাক
উদাহরণ ১
ইনপুট - start = 230, end = 270
আউটপুট - পার্থক্য প্রাইম হলে সংখ্যা: ৬
ব্যাখ্যা - ২৩০ থেকে ২৭০ পর্যন্ত শর্ত পূরণকারী সংখ্যাগুলো:
- 240 (4-2=2)
- 250 (5-2=3)
- 251 (5-3=2)
- 261 (6-3=3)
- 262 (6-4=2)
- 270 (7-2=5)
পার্থক্যগুলো ২, ৩, ৫ — সবই প্রাইম।
উদাহরণ ২
ইনপুট - start = 1101, end = 1120
আউটপুট - পার্থক্য প্রাইম হলে সংখ্যা: ১
ব্যাখ্যা - ১১০১ থেকে ১১২০ পর্যন্ত শর্ত পূরণকারী সংখ্যা: ১১২০ (৩-১=২)। ২ প্রাইম।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
ডাইনামিক প্রোগ্রামিং ব্যবহার করে সমাধান করা হয়। অ্যারে arr[size][90][90][2] ব্যবহার করা হয়। size = 10-এর ঘাত, তাই সর্বোচ্চ ইনপুট 10^size।
প্রতিটি রিকার্সিভ কল check(int place, int eve, int od, int temp, vector<int> vec)-এ বাম থেকে ডান ডিজিট ০-৯ দিয়ে নম্বর বানানো হয়।
arr[size][x][y][temp]-এ x = ইভেন পজিশনের ডিজিট সম, y = অড পজিশনের ডিজিট সম। পার্থক্য প্রাইম কিনা চেক করা হয় arr_2[]-র সাহায্যে যেটে ১০০ পর্যন্ত প্রাইম নম্বর রয়েছে।
startএবংendইনপুট নিন।- গ্লোবাল অ্যারে
arr[size][90][90][2]এবং প্রাইম অ্যারেarr_2[]। - ফাংশন
check(...)রিকার্সিভলি অ্যারে পূরণ করে। - যদি
place == vec.size()হয় তবে লাস্ট পজিশন চেক করুন। অড দৈর্ঘ্য হলেswap(od, eve)। পার্থক্যeve-od।arr_2[]-এ প্রাইম খুঁজুন। পাওয়া গেলে ১ রিটার্ন করুন। - যদি
arr[place][eve][od][temp] != -1হয় তবে রিটার্ন করুন। temp_3 = (temp ? 9 : vec[place])।- i=0 থেকে temp_3 পর্যন্ত লুপ: করেন্ট পজিশন অড হলে
set_odd += i, ইভেন হলেset_even += i। রিকার্সিভ কল দিয়ে কাউন্ট আপডেট করুন। - ফাংশন
place_prime(int val)ভেক্টর বানাতে (LSB থেকে MSB), রিভার্স করুন, অ্যারে -1 দিয়ে ইনিশিয়ালাইজ করুন,check(0,0,0,0,vec)কল করুন। - ফলাফল রিটার্ন করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
const int size = 18;
int arr[size][90][90][2];
int arr_2[] = {2,3,5,7,11,13,17,19,23,29,31,37,43,47,53,59,61,67,71,73,79,83,89,97};
int check(int place, int eve, int od, int temp, vector<int> vec) {
int count;
int temp_3;
if (place == vec.size()) {
if (vec.size() & 1) swap(od, eve);
int temp_2 = eve - od;
for (int i = 0; i < 24; i++) {
if (temp_2 == arr_2[i]) return 1;
}
return 0;
}
if (arr[place][eve][od][temp] != -1) return arr[place][eve][od][temp];
if (temp) temp_3 = 9;
else temp_3 = vec[place];
for (int i = 0; i <= temp_3; i++) {
int set_temp = temp;
int set_even = eve;
int set_odd = od;
if (i < vec[place]) set_temp = 1;
if (place & 1) set_odd = set_odd + i;
else set_even = set_even + i;
count += check(place + 1, set_even, set_odd, set_temp, vec);
}
return arr[place][eve][od][temp] = count;
}
int place_prime(int val) {
vector<int> vec;
while (val) {
vec.push_back(val % 10);
val = val / 10;
}
reverse(vec.begin(), vec.end());
memset(arr, -1, sizeof(arr));
int count = check(0, 0, 0, 0, vec);
return count;
}
int main() {
int start = 20, end = 80;
int count = place_prime(end) - place_prime(start - 1);
cout << "Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: " << count;
return 0;
}
উপরের কোড রান করলে নিচের আউটপুটটি পাওয়া যাবে:
আউটপুট
Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: 15
