Truly magical numbers
All submissions for this problem are available.
Prashant thinks that the number 142857 is magical. When he multiplies the number with 2, he gets 285714 which is a permutation of the digits of the original number. On multiplying with 3,4,5 and 6 too he observes a similar behaviour.
Now Prashant wants to find out truly magical numbers. A truly magical number of order N is a number P with the following properties:
- P should have N digits and the first digit should be non-zero
- On multiplying the number with any i such that 1<=i<=k, the result should be a permutation of the digits of P
- There should not exist any N digit number Q (without leading zeros) with the property that for all i such that 1<=i<=k+1, Q*i is a permutation of digits of Q (Here k has the same value as in the previous point)
- N should not have consecutive zero digits anywhere
It is easily seen that P=142857 is indeed a truly magical number of order 6. P has no leading zeros or consecutive zeros appearing anywhere. For 1<=i<=6, P*i is a permutation of digits of P. Also, there does not exist any number Q such that for all 1<=i<=7, Q*i is a permutation of digits of Q.
Given an integer N, find a truly magical number of order N. Note that for certain values of N there may be more than one truly magical number of order N. In such a case, it is enough to output any one of the truly magical numbers of order N.
The first line of input contains an integer T (<=100), the number of test cases to follow.
Following this are T lines, each containing an integer N, 250<=N<=40000
Output T lines, each containing a truly magical number of order N
The input limits are such that an example cannot be shown here. However, to explain the formatting of the input and output, we show here a sample case that has N outside the input limit range
Input: 2 2 6 Output: 13 142857
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO, NODEJS|
Fetching successful submissions
If you are still having problems, see a sample solution here.