এই প্রোগ্রামে, আমাদের Q সংখ্যক কোয়েরি দেওয়া আছে, প্রতিটি কোয়েরিতে একটি পজিটিভ পূর্ণসংখ্যা N থাকে। আমাদের কাজ হলো C++-এ সংখ্যার সব ফ্যাক্টরের অড ডিজিট সমের যোগফলের কোয়েরি সমাধান করা।
সমস্যা বর্ণনা − প্রতিটি কোয়েরি সমাধানের জন্য, সংখ্যা N-এর সব ফ্যাক্টর বের করতে হবে। তারপর যেসব ফ্যাক্টরের ডিজিট সম বিজোড় (odd) হবে, তাদের যোগফল বের করে প্রতিটি কোয়েরির জন্য রিটার্ন করতে হবে।
উদাহরণ দিয়ে বুঝি,
ইনপুট
Q = 2, queries = {15, 8}আউটপুট
8 1
ব্যাখ্যা
কোয়েরি ১: N = 15, ১৫-এর ফ্যাক্টরগুলো হলো 1, 3, 5, 15।
ফ্যাক্টরগুলোর বিজোড় ডিজিটের যোগফল = 1 + 3 + 5 = 8
কোয়েরি ২: N = 8, ৮-এর ফ্যাক্টরগুলো হলো 1, 2, 4, 8।
ফ্যাক্টরগুলোর বিজোড় ডিজিটের যোগফল = 1 = 1
সমাধান পদ্ধতি
এই সমস্যা সমাধানের জন্য, সব সংখ্যার বিজোড় ডিজিট সম বের করতে হবে। তারপর ফ্যাক্টরগুলো বের করে বিজোড় ডিজিট সম যোগ করতে হবে। এই ডিজিট সমের প্রক্রিয়াকে সহজ बनाने 위해 প্রি-কম্পিউটেড মান ব্যবহার করা যায়। উদাহরণস্বরূপ, ৪১-এর ডিজিট সম = ৪-এর বিজোড় ডিজিট সম + ১-এর বিজোড় ডিজিট সম।
oddDigitSum অ্যারে তৈরী করার পর, দেওয়া সংখ্যা যেসব সংখ্যা দিয়ে বিভাজ্য, তাদের oddDigitSum অ্যারে থেকে যোগ করুন।
সমাধানের কোড উদাহরণ,
উদাহরণ
#include <iostream>
using namespace std;
#define N 99999
void calcOddDigitSum(int oddDigitSum[]) {
for (int i = 1; i < N; i++)
oddDigitSum[i] = oddDigitSum[i / 10] + (i & 1) * (i % 10);
}
void findFactorSum(int oddDigitSum[], int factorSum[]) {
for (int i = 1; i < N; i++)
for (int j = i; j < N; j += i)
factorSum[j] += oddDigitSum[i];
}
int main(){
int Q = 3;
int query[] = { 5, 154, 98 };
int oddDigitSum[N];
int factorSum[N];
calcOddDigitSum(oddDigitSum);
findFactorSum(oddDigitSum, factorSum);
for (int i = 0; i < Q; i++)
cout<<"For query "<<(i+1)<<": The sum of odd number digit sums of all the factors of a number is "<<factorSum[query[i]]<<endl;
return 0;
}আউটপুট
For query 1: The sum of odd number digit sums of all the factors of a number is 6 For query 2: The sum of odd number digit sums of all the factors of a number is 31 For query 3: The sum of odd number digit sums of all the factors of a number is 27
