1 <= A < 10^15
1 <= S <= 135
আমরা যদি A পর্যন্ত সকল সংখ্যা generate করি এবং sum এর সমান কিনা তা check করি তাহলেই আমরা আমাদের answer পেয়ে যাব।
1 <= S <= 135
আমরা যদি A পর্যন্ত সকল সংখ্যা generate করি এবং sum এর সমান কিনা তা check করি তাহলেই আমরা আমাদের answer পেয়ে যাব।
000
001
.
.
188
189
.
.
244
245
.
.
257
258
আমাদের কে প্রথমে জানতে হবে ডিজিট সংখ্যা কয়টি। এখানে আমরা ৩ ডিজিট এর সংখ্যা ধরেছি A।
আমরা ৩ ডিজিট এর সকল সংখ্যা generate করতে পারব। কিন্তু A এর উপরের সংখ্যা generate করে আমাদের কোন লাভ হবে না। তাই A পর্যন্ত limit দিয়ে ৩ ডিজিট এর সংখ্যা generate করব।
আমরা আগেই n ডিজিট এর সকল সংখ্যা কিভাবে generate করা যায় তা দেখেছি এখানে।
এখন আমরা দেখবো A পর্যন্ত limit কিভাবে সেট করা যায়।
আমরা একটা recursive function লেখতে পারি। যার প্যারামিটার হবে 3ta current_digit_no ,sum_left , limit ।
আমরা এভাবে চিন্তা করতে পারি A = 2(0 তম ডিজিট ) 5 (1 তম ডিজিট) 6 (2 তম ডিজিট) 8 (3 তম ডিজিট)।
function er limit parameter আমাদের বলবে আমরা যে ডিজিট এ আসছি তার limit পর্যন্ত নিতে পারব না সব সংখ্যা নিতে পারব।
০ তম ডিজিট এর জন্য আমরা highest ২ পর্যন্ত generate করতে পারব, আমরা যদি ০ তম ডিজিট এ ২ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ৫ পর্যন্ত genetare করতে পারব, আবার আমরা যদি ০ তম ডিজিট এ ০/১ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ০-৯ পর্যন্ত সব গুল ডিজিট নিয়ে আগাইতে পারব। পরের ডিজিট এর জন্য same কাজ হবে।
আমরা limit এর ২টা value ঠিক করব।
যখন limit == 0 তখন প্রতিবার ০ - ৯ এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব আর limit 0 পাথাব।
আর যখন limit == 1 তখন ঐ ডিজিট এর highest_limit বের করব। প্রতিবার ০ ঠেকে highest_limit এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব। সংখ্যাটা highest_limit এর চে ছোট হলে limit = 0 পাঠাব আর highest_limit এর সমান হলে limit = 1 পাঠাব।
BaseCase:
যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ হয়ে যায় তার মানে আমরা এমন একটা n ডিজিট বিশিষ্ট সংখ্যা পায়ে গেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান। তাই আমরা ১ return করব।
যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ না হয় তার মানে আমরা যে সংখ্যা generate করেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান না। তাই আমরা ০ return করব।
dynamic programming:
function টার recursive tree আঁকলে দেখবো যে এখানে overlapping subproblem পাওয়া যাবে। তাই যদি আমরা memorization করতে পারি।
No comments:
Post a Comment