PROBLEM LINK: CodeChef: Practical coding for everyone
DIFFICULTY: EASY
PROBLEM
Given a 3-digit number K whose all digits are non-zero and a number N.The number K is fed to a machine which performs the following operation: Take in a 3-digit number, multiply it by 7,11 and 13 consecutively and use the digits of the product to form all possible 3-digit numbers. All these 3-digit numbers are again fed to the machine and this process is done for N iterations. Over all these steps, how many different 3-digit numbers are output by the machine?
EXPLANATION
Note that 13*11*7=1001=1000+1. Now consider any three digit number ABC. Any such number multiplied by 1001 will give ABCABC as output. Now, any of the numbers that can be output by the machine consists of the digits of ABCABC which are the same as the digits of the original number,i.e., A,B and C.
The number may go through the machine any number of times, but each time the numbers output by the machine contain only the digits A,B and C. Also, by observation, we may see that after 5(N>=5) iterations, all possible 3-digit numbers that can be generated would have been generated. So, the required answer is the number of 3-digit numbers that can be formed by using the digits A, B and C only.
Suppose all three digits of K are different. Then, all 3 places can have any 3-digits and answer=3*3*3=27. If any two digits of K are the same, then the answer is 2*2*2=8.If all the three digits are the same, then the answer is 1*1*1=1.