Timus 1014 : Product of Digit

Prob link: Timus 1014: Product of Digit

প্রব্লেম এ চাওয়া হয়েছে যে , আমাকে একটা integer দেয়া হবে, আমাকে minimum এমন একটা integer বের করতে হবে যেখানে ঐ integer এর প্রত্যেক digit এর গুনফল ঐ integer এর সমান হয়।
test case চিন্তা করলে দেখা যায়, N = 10 ;
10 কে এভাবে লিখা যায়ঃ (2 * 5) , (5 * 2) .. দেখা যাচ্ছে যে আসলে 10 এর গুননীয়ক গুলা নিয়ে আমাদের চিন্তা করা লাগবে। দেখা যাচ্ছে  25 , 52 ,... 25 হচ্চে সবচেয়ে ছোট, তাই answre 25 for N = 10;

আমরা কিন্ত ( 1 * 10 ) এই combination টা নেইনাই , কারন 1,1,0 or 1,0,1 এর digit এর গুনফল N এর সমান হয়না।

এখন এটা solve করা যায় কিভাবে ? প্রশ্নে এ বলা হইছে digit এর গুনফল  N এর সমান হবে, এরমানে একটা জিনিস বলা যায় যে আমার উত্তর আসলে 0 to 9 digit এর কোন সংখ্যা হবে।
তাহলে loop এর code অনেকটা এরকম হবেঃ

for ( int digit = 9 ; digit > 1 ; digit -- )

{

         // rest of the code

}

তাহলে তো প্রব্লেম টা খুবই সহজ হয়ে গেলো। আমাদের দেখতে হবে যে 2 থেকে 9 এর মাঝে কোন কোন digit দিয়ে N কে mod করা যায়, মানে ভাগশেষ শুন্য হয়। যখনই কোন সংখ্যা দিয়ে N ভাগ যাবে ঐ সংখ্যা দিয়ে N কে ভাগ করতে থাকতে হবে যতক্ষন N  আর ভাগ না যায়।

 অর্থাৎ,

while ( N % digit ==0 )

আমাদের মূল কাজ হল N এর divisor digit গুলি বের করা,মানে যেসব digit দিয়ে N কে মড করা যায় এমন digit.

এখন যেহেতু আমাদের নতুন একটা integer বের করতে হবে, কাজেই কেবলমাত্র একবার N কে মড করার পরেই থেমে গেলে হবে না, যতক্ষন মড করা যায় করতে থাকতে হবে। কাজেই , while লিখা হয়েছে।
উদাহরন দিলে ব্যাপারটা বোঝা সহজ হবে ,
N = 50  >>  ans = 255
N = 120 >> ans = 358

( Digit নিয়ে কাজ করার এইটা একটা reason , অনেকে Digit না নিয়ে only sqrt ( N ) পর্যন্ত লুপ চালায়ে first যেটা দিয়ে ভাগ যায় সেই সংখ্যা আর  N /  ( সেই সংখ্যা ) ans print করে , যা ভুল ; 120 এর জন্য খেয়াল করলেই বুঝা যায়ঃ

for ( int digit = 2 ; digit <= 9 ; digit++ ){
if ( N % digit == 0 ) {
cout << digit << N / digit << endl ;

                    return 0;

           }

}

120 এর জন্য হবে 260 ,যেটা ভুল কারন  2 * 6 * 0 == 0  ( not 120 )

valid code:

for ( int digit = 9 ; digit > 1 ; digit-- ){
       while ( N % digit == 0 ){
       // rest of the calculation
       }
}
এখন হিসাবের জন্য N = ১০ ধরি,
---> 10 % 5 == 0
কাজেই এটি while লুপ এ ঢুকবে। লুপের ভিতর আমরা দেখি যে 5 একটি ভ্যালিড ডিজিট আমাদের ফাইনাল রেজাল্ট এর জন্য, তাই আমরা 5 কে আমাদের প্রথম ডিজিট হিসেবে নিয়ে একটি ভ্যারিয়েবল ( SUM ) এ সেইভ করে রাখবো।এখন SUM এর মান 5, কাজেই আমাদের এখন N কে 5 দিয়ে ভাগ করতে হবে, কেননা আমরা 5 কে আমাদের ডিজিট হিসেবে নিয়ে নিয়েছি।

কাজেই N = N / 5 = 2

এরপর আমরা আবার দেখবো N % 2 == 0, কাজেই আমরা আমদের পরের ডিজিট টিও পেয়ে গেলাম।

 ( আশা করি এতক্ষনে সবাই বুঝে গেছি আমরা কেন লুপ ৯ থেকে ২ পর্যন্ত চালিয়েছি। )

কাজেই আমাদের ফাইনাল রেজাল্ট হবে এরকমঃ
25  =  2 * 10 + 5 * 1 ( multiple করার ব্যাপারটা তোমরা নিজেরা try করে দেখো )
অর্থাৎ রেজাল্ট = 25।
120 এর জন্য :  3 * 100 + 5 * 10 + 8 * 1 = 358.

Critical test case:

N = 0 হলে আমাদের রেজাল্ট হবে 10, কারন 0 পজিটিভ, নেগেটিভ কোনটিই না এই প্রব্লেম এর জন্য। কাজেই 10 হচ্ছে প্রথম পজিটিভ রেজাল্ট।
N = 1 হলে রেজাল্ট হবে 1.
এখন N যদি প্রাইম নাম্বার হয়? এখানে একটি কন্ডিশন আছে, যা লুপ এর শেষে N কে চেক করে, আমরা এটি বুঝতে পারছি যে, লুপের শেষে N যদি 1 হয়, তাহলে আমাদের ফাইনাল অ্যান্সার হবে -1, কারন কোন ডিজিট ই N কে মড ( MOD ) করতে পারেনি। এটি আশা করি সবাই বুঝে গেছো।

ধন্যবাদ কষ্ট করে পড়ার জন্য।