# Forum

28.04.2009   # 1
CodeFu 2009 Round 1 - Shortest 500 Solution
Shortest solution is the one that is correct for all input test cases, but has the smallest number of non blank characters.

For e.g.
``public class PowerOfThree {  public int nthElement(int N) {    int power = 1;    int sum = 0;    for (int i = 0; i < 31; ++i) {      if ((N & (1<<i)) == (1<<i)) {        sum += power;      }      power *= 3;    }    return sum;  }}``

has 148 non blank characters.

The winner is the one who has the smallest number of characters and the solution passes on ALL test cases.
In case of two solutions with the same number of characters, the winner is the one who has submitted earlier.

Post your solutions of the problem 500 here.
Be sure to test the solution in the Practice room first.

The contest is active until May 10th 12:00 (noon), and the winner will receive the new CodeFu T-Shirt.
28.04.2009   # 2
Well, if no one else is going to post something obvious(ly not the winning solution)...

``public class PowersOfThree {  int s, i, p = 1;  public int nthElement(int N) {    for (; i < 31; ++i, p *= 3)      if ((N & 1<<i) == 1<<i)        s += p;    return s;  }}``

28.04.2009   # 3
previouse one is 114 i think...

``public class PowersOfThree {  int s, i, p = 1;  public int nthElement(int N) {    for (; i < 31; ++i, p *= 3)      if ((N & 1<<i)!=0)         s += p;    return s;  }}``

111
28.04.2009   # 4
vasja's solution is 111

Just as info, the lengths of solutions; from the 4 competitors who solved 500 correctly are:
[list]igorkulev 627[/list]
[list]hsilomedus 311[/list]
[list]palikrushev 778[/list]
[list]martinancevski 180[/list]

Of course, they coded the solutions to work correctly and not for the smallest length, but still, they are quite small.

Awaiting for other submissions to the shortest 500 solution.
There are for sure more things that can be done to make it smaller.
Who can do it in less than 100 characters?
28.04.2009   # 5
109
``public class PowersOfThree {  int s, i, p = 1;  public int nthElement(int N) {    for(;i<31;p*=3)      if ((N & 1<<i++)!=0)        s += p;    return s;  }}``
29.04.2009   # 6
108 hmm less than 100 ... gonna need a new idea
``public class PowersOfThree {  int s, i, p = 1;  public int nthElement(int N) {    for(;i<31;p*=3)      if ((N & 1<<i++) > 0)        s += p;    return s;  }}``
29.04.2009   # 7
105
``public class PowersOfThree {  public int nthElement(int N) {    int L=1,p=0;    for(;N>0;L*=3,N/=2)      if(N%2>0)        p+=L;    return p;  }}``
29.04.2009   # 8
``public class PowersOfThree {  int p=1, s;   public int nthElement(int N) {    for(;N>0;p*=3,N/=2) s+=N%2*p;    return s;  }}``

98
29.04.2009   # 9
And for the record, what is your top score?

Just for motivation++
29.04.2009   # 10
hsilomedus wrote:
And for the record, what is your top score?

Just for motivation++

For the moment, it is 87.
I am still working on some ideas.
29.04.2009   # 11
``public class PowersOfThree {  public int nthElement(int N) {     return N>0?N%2 + 3*nthElement(N/2):0;  }}``

87

Recursion rules!
29.04.2009   # 12
Man i tried the ?: operator in java previously and got error so i thought its only for c++
29.04.2009   # 13
hsilomedus wrote:
``public class PowersOfThree {  public int nthElement(int N) {     return N>0?N%2 + 3*nthElement(N/2):0;  }}``

87

Recursion rules!

Cool, very nice.
Now the real challenge begins
Let us see if someone can do it in 86 characters.
Anything is allowed, as long as the solution passes the test cases.
30.04.2009   # 14
anikov wrote:
Shortest solution is the one that is correct for all input test cases....

Will there be any test cases with N < 0 ?
30.04.2009   # 15
azder wrote:
Will there be any test cases with N < 0 ?

No.
Constraints for N, as defined in the problem statement, are:
N will be between 1 and 1000000 (one million) inclusive.