First we need to find the prime factorization of N. If there is a factor greater than 7 than the answer is -1 for sure. Obviously the less digits our answer has the smaller it will be so if for example we got 2 3s , it is better to save it as one 9 in the answer. The same goes for other digits like 2 ( 3 2s can be kept as 1 8). Our answer will be a sequence of digits, (we will not care for their order until we get all the necessary digits). First of all we need to take 2 3s and push 9 to our answer . We might be down to 1 or 0 3s in the end, and then we have to check that case individually. We need to take triples of 2s and add 8s, in this case we might be down to 3 cases where there is no 2 left of there is one left or there are two 2s left. And then we might need to check for the case of 6 (if we have 1 3 and at least 1 2). For skipping all those unnecessary conditions we can take the number 9, see how many times our N can be divided to 9 and accordingly add the digit 9 to our answer, then the same for 8 then 7 ..... until we finish with 2. If after all those operations our number is still greater than 1 that means that there is a factor which we can't express as one digit. Then when we have gathered all the necessary digit which after being multiplied will give us N, we need to sort them in ascending order and output the answer. NOTE THIS IS A BIG ONE : the case of 0 is tricky. Some people output 0 . It is not correct because the task says that our answer must be a positive integer and 0 is not considered as positive. Some people output -1 which is also wrong because if there is one digit 0 in our answer than the product will give 0, so in case of 0 the answer is 10.
No comments:
Post a Comment