Picking the odd number out

Question

I want to write a method that returns the last odd position available that has not been removed. For example

Say the number inputted to function is 5 Then we can number as follows 1,2,3,4,5

After first pass, numbers left are - 2,4. 1,3,5 have been removed After second pass - 2 has been removed and so we are left with 4

The function should return 4. In my method, I create an array of n numbers. Each element may either have a value 0 or 1, 0 representing that element not being removed and 1 being removed.My code is

int findposition(int n)
{
int barr[n];
int count=0,i,begIndex=0;

for(i=0;i<n;i++)
    barr[i]=0;

while(n!=count+1)
{
    for(i=begIndex;i<n;i=i+2)
    {
        barr[i]=1;
    }


    for(i=0;i<n;i++)
    {
        if(barr[i]==0)
            begIndex=i;
    }

}

return (begIndex+1);
}

The above function compiles successfully, but does not print anything when called from main method. Also, I think my approach is a bit clumsy. Can there be a more neater way to do this.

What it should return is no use. Why is the two removed? Why are the odd number's removed? Programming has to be general, not specific. — Linuxios, Jul 19 '12 at 17:21
`while(n!=count+1)` will loop endlessly unless the function is passed in `1`, in which case it wouldn't execute at all. — chris, Jul 19 '12 at 17:23
If I understand the question correctly, the solution boils down to finding the most significant bit of the input number. There are a few bit twiddling hacks to achieve this if you google for it. — nhahtdh, Jul 19 '12 at 17:24
Linuxios: Do you mean that I should take an input form the user and remove evry `k`th element until we reach the last element. — OneMoreError, Jul 19 '12 at 17:25
Follow up my comment from before: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog — nhahtdh, Jul 19 '12 at 17:32
This sounds alot like homework. As do many of your other questions. — Aaron Gray, Jul 19 '12 at 17:45

nhahtdh · Answer 1 · 2013-01-27T21:12:06.397

1

If I understand the question correctly, the solution boils down to finding the most significant bit of the input number. This is simply Josephus problem with k = 2.

edited Jan 27 '13 at 21:12

answered Jul 19 '12 at 17:22

nhahtdh

55,989
15
126
162

score 1 · Answer 2 · answered Jul 19 '12 at 17:34

1

If you take a look at the indices of the removed objects in the binary positional notation, you'll find out that in the first step you remove all the numbers which have a 1 as the last digit. This leaves us with numbers of form xxxx0, where xxxx are all binary digits in some range. So you will have like 001 0, 010 0, 011 0, 100 0. It's obvious that the second step removes all the numbers that have the suffix 10 and you'll end up with 01 00, 10 00, 11 00 etc.

Apparently the last number standing is the one having the most trailing zeroes.

answered Jul 19 '12 at 17:34

Adrian Panasiuk

7,249
5
33
54

1

And to take this one step further, this number is equivalent to the input number's MSB with all other bits set to zero. That can be done as described [here](http://stackoverflow.com/a/994709), which would be a hilarious response to this (presumably) homework problem. Other students would be busy learning the semantics of loops, while this student turns in `return (1 << __builtin_clz(n));`. Gets low grade because this doesn't work on some compilers. – Kevin Vermeer Jul 19 '12 at 17:53

Picking the odd number out

2 Answers2