Forum

Post 28.04.2009   # 1
Subject 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 7-th 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:
public class PowersOfThree {
public int nthElement(int N) {
int power = 1;
int sum = 0;
for (int i = 0; i &lt 31; ++i) {
if ((N & (1<<i)) == (1<<i)) {
sum += power;
}
power *= 3;
}
return sum;
}
}
bilievsk is offline Reply

Please login to post reply.