1. ## Codechef exercise

This is not me asking for the answer, I have working code which uses an array list but it is too slow to pass the submission, the link isOdd | CodeChef

My code is below:
Java Code:
```import java.util.*;
import java.io.*;

public class Main {
public static ArrayList<Integer> remove0(ArrayList<Integer> al1) {
for(int i = 0; i < al1.size(); i++){
if(al1.get(i) == null){
continue;
}
else if(al1.get(i) == 0){
al1.remove(i);
}
}
return al1;
}
public static ArrayList<Integer> tRemove(ArrayList<Integer> al) {
if(al.size() == 2){
return al;
}
else{
for(int i = 0; i < al.size(); i++){
if(al.get(i) == null){
continue;
}
else if(i % 2 != 0){
al.set(i, new Integer(0));
}
}
remove0(al);
return tRemove(al);
}
}
public static void main(String[] args) throws IOException{
ArrayList<Integer> people = new ArrayList<Integer>();
//Scanner in = new Scanner(System.in);
for(int j = 0; j < cases; j++){
people.clear();
System.out.print("Enter a number of crew members");
//int input = in.nextInt();
for(int i = 0; i <= input; i++){
if(i == 0){
}
else{
}
}

/*for(Integer i : people){
System.out.println(i);
}*/
//System.out.println();
tRemove(people);
/*for(int i = 1; i < people.size(); i++){
System.out.print("Index " + i + " is ");
System.out.println(people.get(i));
}*/
System.out.println(people.get(1));
}
}
}```
Unfortunately it is not efficient enough since it has so much to do every time a number is input. Once it is expected to work on numbers over 1 million it takes a few seconds or more. I am trying to make this more efficient, unfortunately I cant think of a way to manipulate numbers alone and the easiest way for me is to populate an arraylist then make changes. Any help on, I guess, the number theory to solve this problem?

2. Member
Join Date
Jan 2011
Posts
13
Rep Power
0
Google the Josephus problem, that's what it looks like.

3. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
Any help on, I guess, the number theory to solve this problem?

Think about the case where there are 12 people. We can number them as in the question and also write those numbers in binary:

Java Code:
```1 2 3 4 5 6 7 8 9 10 11 12
- - - - - - - - - -- -- --
1 1 1 1 1 1 1 1 1 1  1  1
0 1 0 0 1 1 0 0 0  0  1
0 1 0 1 0 0 1  1  0
0 1 0  1  0```
Notice how the first round losers (1,3,5,...) all end in a 1.

Let's remove them, and also remove the trailing zero from the rest.

Java Code:
```  2   4   6   8   10    12
- - - - - - - - - -- -- --
1   1   1   1   1     1
0   1   0   0     1
0   1     0```

Now we notice that the pattern merely repeats itself - the second round losers will be those (2,6,10) that end with a 1.

And so it goes until we have a winner: the person who has the largest number of trailing zeros.

These "winning" numbers have a 1 followed by lots of zeros.

You might want to think about these winning numbers (in binary they are 1,10,100,1000, etc) because there's a pattern to them that you can exploit.
Last edited by pbrockway2; 01-24-2011 at 01:41 AM.

4. wow, that's definitely a very helpful way to approach it, my thought is to count the number of trailing zeros with a loop and str.substring, after converting each number to binary string.

I feel like that is fairly inefficient however, for a number like 100, it would have to first loop through 100 items, then loop through each string which can contain a length of 7, I'm a little unfamiliar with bit manipulation and the operators for them and using tobinarystring is the best I can think of right now, I suppose I will have to browse the binary operators api.

5. Senior Member
Join Date
Nov 2010
Posts
210
Rep Power
7
At the risk of giving too much away, it seems that the << operator is key to this problem.

6. Member
Join Date
Jan 2011
Posts
13
Rep Power
0
Another approach maybe, although not fully proven. For:

round 1: 1 2 3 4 5 6 7 8 12
round 2: 2 4 6 8
round 3: 4 8
round 4: 8

For 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
round1: 2 4 6 8 10 12 14 16 18 20
round2: 4 8 12 16 20
round3: 8 16
round4: 16

Looks like for n = 1, keep doubling n ( same as a shift left ) until n > number of people. The previous position at loop end n/2 or the highest power of 2 < number_of_people is the position you want to stand in.

Java Code:
```long number_of_people = 21;
long n = 1;

while( n < number_of_people )
{
n = n * 2;
}

int position_to_stand_in = n/2;```
Although of course I could be wrong :)

7. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
the highest power of 2 < number_of_people is the position you want to stand in.

Yes, what I calling "winning" numbers are all powers of 2.

Rather than using loops, remember that there are logarithms available. (And BigInteger has a bitLength() method.)

8. Alright, I think I got it figured out, so it simply comes down to finding the largest power of 2 that is less than the input.

9. Member
Join Date
Jan 2011
Posts
13
Rep Power
0
At first appearance that's what it looks like, although to correct myself, it should be <= input I think rather than < input.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•