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 টা নেইনাই , কারন 110 or 101 এর 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

}

}

For calculation part let’s see for N = 10 how does the code works,

—> 10 % 5 == 0

so it will enter inside while loop. Inside loop we get that 5 is a valid digit for our final result, so we will take 5 as our first digit and store it in a variable say SUM ,

so now SUM = 5, then we have to divide N by 5 as we have already taken 5 as our digit,

so N = N / 5 . so now N = 2;

then again we see that N % 2 == 0 so we get our next digit ( আশা করি এতক্ষনে সবাই বুঝে গেছি আমরা কেন লুপ ৯ থেকে ২ পর্যন্ত চালিয়েছি। )

now we get our second digit 2 so our final sum will be 25 which can be written like this :

25  =  2 * 10 + 5 * 1 ( multiple করার ব্যাপারটা তোমরা নিজেরা try করে দেখো )

so answer is 25 ;

again for 120 answer is  3 * 100 + 5 * 10 + 8 * 1 = 358.

Critical test case :

N = 0 , answer is 10  ( 0 is neither a positive or a negative number for this problem, so 10 is the first non-negative digit )

for N = 1 answer is 1

And what if N is a prime number ? There lies a last condition that checks the value of N after the loop. I guess you all clearly understand now if N != 1 then the answer will be -1 as no digit could MOD the desired N , hence N may or may not be prime :p

সবাই AC করায় ফেল 🙂

Advertisements