দেওয়া অঙ্ক সংখ্যা ও অঙ্ক যোগফলের সাথে সর্বোচ্চ সংখ্যা বের করা (C++)

সমস্যা বিবরণ

দুটি পূর্ণসংখ্যা N (অঙ্ক সংখ্যা) এবং sum (অঙ্ক যোগফল) দেওয়া আছে। আমাদের কাজ হল N অঙ্কের সাবচেয়ে বড় সংখ্যা বের করা যেন তার অঙ্কগুলোর যোগফল sum হয়।

উদাহরণ

ইনপুট: N = 3, sum = 15
আউটপুট: 960

পদ্ধতি ১: ব্রুট ফোর্স (অপ্রচলিত)

সবচেয়ে বড় N-অঙ্কের সংখ্যা থেকে নিচে নেমে যোগফল চেক করা।

পদ্ধতি ২: গ্রিডি পদ্ধতি (O(N)) - সেরা

MSB থেকে LSB পর্যন্ত প্রতিটি ডিজিটে সম্ভাব্য সর্বোচ্চ মান (৯ বা বাকি sum) বসানো।

#include <iostream>
using namespace std;

int findLargestNumWithSum(int N, int sum) {
    if(sum==0 || sum > 9*N) return -1;
    int num=0;
    for(int i=0;i= 9){ num = num*10 + 9; sum -= 9; }
        else { num = num*10 + sum; sum=0; }
    }
    return num;
}

int main() {
    cout << findLargestNumWithSum(3, 25); // 997
    return 0;
}