সি++-এ প্রদত্ত ডিজিট সংখ্যা ও ডিজিট সমষ্টি দিয়ে সর্বনিম্ন সংখ্যা বের করা

এই সমস্যাতে, আমাদের দুটি মান দেওয়া আছে: সমষ্টি (sum) যেটি ডিজিটগুলোর যোগফল বোঝায় এবং ডিজিট (digit) যেটি ডিজিটের সংখ্যা বোঝায়। আমাদের কাজ হলো প্রদত্ত ডিজিট সংখ্যা এবং ডিজিট সমষ্টি বিশিষ্ট সর্বনিম্ন সংখ্যা বের করা।

উদাহরণ দিয়ে সমস্যা বোঝা যাক,

ইনপুট

sum = 15, digit = 2

আউটপুট

69

ব্যাখ্যা

সমষ্টি ১৫ বিশিষ্ট সব ২-ডিজিট সংখ্যা: ৬৯, ৭৮, ৮৭, ৯৬।

সমাধানের পদ্ধতি

একটি সহজ সমাধান হলো ডিজিট কাউন্ট অনুযায়ী সব সংখ্যা বিবেচনা করে সবচেয়ে ছোট সংখ্যা বের করা যার ডিজিট সমষ্টি প্রদত্ত সমষ্টির সমান।

একটি কার্যকর সমাধান হলো লালসামূলক (greedy) পদ্ধতি। আমরা সংখ্যাটি শেষ ডিজিট (LSB) থেকে তৈরি করব। আমরা LSB-এর জন্য সম্ভাব্য সর্বোচ্চ মান বিবেচনা করব এবং তারপর পরবর্তী পজিশনের জন্য যাব। আমরা চেষ্টা করব LSB কে যতটা সম্ভব বড় এবং MSB কে যতটা সম্ভব ছোট রাখতে।

সমাধান কোড:

উদাহরণ

#include <iostream>
using namespace std;

void findSmallestNumWithSum(int digit, int sum) {
    if (sum == 0) {
        if(digit == 1)
            cout<<"Smallest number is 0";
        else
            cout<<"Smallest number with sum cannot be found";
        return;
    }
    if (sum > 9*digit) {
        cout<<"Smallest number with sum cannot be found";
        return;
    }
    int number[digit];
    sum -= 1;
    for (int i = digit-1; i>0; i--) {
        if (sum > 9) {
            number[i] = 9;
            sum -= 9;
        } else {
            number[i] = sum;
            sum = 0;
        }
    }
    number[0] = sum + 1;
    cout<<"Smallest number is ";
    for (int i=0; i

আউটপুট
Smallest number is 159