Digital Root & Digit Sum

#Digit Root:
কোনো অঋণাত্মক সংখ্যার ডিজিটগুলো যোগ করতে করতে একটা ডিজিট পেলে তাকে ঐ সংখ্যার Digital Root বলে। যেমনঃ  345 = 3 + 4 + 5 =  12 = 1 + 2 = 3 , এখানে 3 , 345 এর Digital Root.

এছাড়াও আমরা কোনো নাম্বার mod 9 করে তার Digital Root বের করতে পারি। [এর ব্যাখ্যা এই লিঙ্ক এ পাব]
যেমনঃ 345 mod 9 = 3

এখন আমরা খুব সহজেই এর জন্য উপরের যেকোনো একটি উপায়ে একটি সংখ্যার Digital Root বের করতে পারব।
ধরি, DigitRoot(int n) একটা ফাংশন যা Digital Root বের করবে।
অতএব, শর্ত গুলো হবে-
DigitRoot(int n)
{
          int digit;
          if(n==0)
                 digit = 0;
          else if(n%9==0)
                 digit = 9;
          else
                digit = n % 9;
}


#Digit Sum:
Digit Root বের করতে আমরা আরেকটা concept এর সাথে পরিচিত হই তা হচ্ছে Digit Sum।
345 এর Digit sum = 3 + 4 + 5 = 12.
এখন, এখানে মজার বেপারটি হচ্ছে কেউ যদি আমাকে বলে কোন সংখ্যার digit sum 13 হলে 3 digit এর মধ্যে এই সংখ্যাটি maximum কত হতে পারে?? এটা কেম্নে বের করবো!! :|
আচ্ছা আগে আমরা বের করব 3 digit এর maximum নাম্বারটির digit sum কত, 3 digit এর maximum number 999 ,এর digit sum = 27,সুতরাং 3 digit এর কোন সংখ্যার digit sum 27 এর বেশি হতে পারবে না ,তাই 13 digit sum এর একটা সংখ্যা অবশ্যই আছে যার digit 3. আমরা এখন একটি কাজ করব তা হচ্ছে 3 digit এর সংখ্যাটি আমরা left to right একটা একটা করে digit বের করব।
ধরি, a = 13 (digit sum)
সুতরাং, ১ম digit হবে = min(9, a)
              a = a - ১ম digit
                 = 13 - 9 = 4
            ২য় digit = min(9,a)
             a = a - ২য় digit
                = 4 - 4 = 0
            ৩য় digit = min(9,a)
             a = a - ৩য় digit
                = 0 - 0 = 0
অতএব, 13 digit sum বিশিষ্ট 3 digit এর maximum number হচ্ছে = 940
একইভাবে আমরা minimum number ও বের করতে পারব।
এখানে ১ম digit হবে = max(10, digit sum - (digit - 1) * 9)
[এখানে 1 হবে leading zero dismiss করার জন্য তারপর থেকে zero use করব।]
            digit sum = digit sum -১ম digit
            digit = digit - 1
এভাবে যে পর্যন্ত digit zero না হবে এই process চলতে থাকবে।

নিচের problem টা করি, তাহলেই বাকি concept clear হয়ে যাবে।-
Given Length and Sum of Digits...