C++-এ n-এর সব dzielন করলে সর্বোচ্চ ডিজিট সম কোনটি?

একটি পূর্ণসংখ্যা n দেওয়া আছে। n-এর সব divizor (ভাজক) বের করে, যেই 디ভাজরের আঙ্কিক যোগফল (ডিজিট সম) সর্বোচ্চ, সেই যোগফল বের করুন।

উদাহরণ

ইনপুট: 18

ডিভাইজর: 1, 2, 3, 6, 9, 18

ডিজিট সম: 1, 2, 3, 6, 9, 9 (১৮ → ১+৮=৯)

আউটপুট: 9

অ্যালগরিদম ১: সিম্পল (O(n))

1. 1 থেকে n পর্যন্ত লুপ।
2. n % i == 0 হলে ডিজিট সম বের করে ম্যাক্স আপডেট।

C++ প্রোগ্রাম (সিম্পল)

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int largestDigitSumDivisor(int n) {
    int maxSum = 0;
    for (int i = 1; i <= n; i++)
        if (n % i == 0)
            maxSum = max(maxSum, calcDigitSum(i));
    return maxSum;
}

int main() {
    int n = 45;
    cout << "The divisor with largest sum of digits is " << largestDigitSumDivisor(n) << endl;
    return 0;
}

আউটপুট

The divisor with largest sum of digits is 9

অ্যালগরিদম ২: অপ্টিমাইজড (O(√n))

ডিভাইজরগুলো জোড়ায় আসে: i এবং n/i। √n পর্যন্ত লুপ চালিয়ে দুটোই চেক করুন।

C++ প্রোগ্রাম (অপ্টিমাইজড)

int largestDigitSumDivisor(int n) {
    int maxSum = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            maxSum = max(maxSum, calcDigitSum(i));
            maxSum = max(maxSum, calcDigitSum(n / i));
        }
    }
    return maxSum;
}

আউটপুট (n=32)

The divisor with largest sum of digits is 8

ব্যাখ্যা: ৩২-এর ডিভাইজর: ১,২,৪,৮,১৬,৩২। ডিজিট সম: ১,২,৪,৮,৭,৫ → ম্যাক্স ৮ (ডিভাইজর ৮)।

কমপ্লেক্সিটি

বড় n (১০^৯+) এর জন্য অপ্টিমাইজড ভার্সন প্রয়োজন।