Forum
28.04.2009  # 1 
CodeFu 2009 Round 1  Problem 500
500. Powers Of Three
The input constraints for N was one million, so it was possible to dynamically generate all the numbers in one big array. Then just return the N element of the array. Here, I will explain how to solve the problem without generating all the numbers. Lets represent the numbers from the generated array in ternary (in base three): 1 = '0001' = 3^0 3 = '0010' = 3^1 4 = '0011' = 3^1 + 3^0 9 = '0100' = 3^2 10 = '0101' = 3^2 + 3^0 12 = '0110' = 3^2 + 3^1 13 = '0111' = 3^2 + 3^1 + 3^0 Since every power of three can be used only once, the ternary representation of every number will have only 0 and 1 as digits (thus it is also a valid binary number). What we can see from this is that if we take the value of the number in ternary, and calculate the value as if this number was binary, we will get the index of that number in the sorted array. For example: 13 = '0111' (in base three). But, '0111' = 7 in base two. This means that the 7th number in the array is 13. So, all we need to do is, take the binary representation of the number N, and get the value of the N as if it was a number in base three. This is the complete solution:


Please login to post reply.