1. ## Last Man Standing

After losing in battle, a ruthless Roman General has N men left, but is cornered on all sides. His only way to escape is a small boat which can carry only two people. He has no option but to select 1 out of the remaining N men to accompany him back to Rome.

He chooses to devise a plan to decide a random winner.

He orders all N soldiers to be numbered and to form a circle in order of their numbers. Number 1 is given a sword and he must kill the next soldier (i.e. soldier Number 2) and give the sword to the next surviving soldier (i.e. soldier Number 3). All soldiers have t do the same until one of them is left. Which soldier survives in the end?

INPUT:
The number N denoting the number of soldiers.

OUTPUT:
The number of the last surviving soldier.

CONSTRAINTS:
0<N<1000000

SAMPLE INPUT #1:
100

SAMPLE OUTPUT #1:
73

SAMPLE INPUT #2:
10

SAMPLE OUTPUT #2:
5

This question is from HP Code Wars 2019 Bangalore.

My issue:
I wrote the code for odd and even inputs of N separately and it works so logically I do know the solution but do I? I tried making a general code for both odd and even inputs and it works but only partially i.e. only for odd inputs and not the even inputs i.e. shows the wrong output. I'm not able to figure out the mistake in my logic and I need help with the entire code for a general case whether ODD or EVEN input.

Don't suggest to use my own ODD and EVEN code like this:

Code:
```int N=cin.get();

if ( N%2==0 )
{
//EVEN NUMBER CODE
}

else
{
//ODD NUMBER CODE
}```
Thanks!

2. Sounds like this rather more classic expression of the same problem.
Josephus problem - Wikipedia

> I'm not able to figure out the mistake in my logic and I need help with the entire code for a general case whether ODD or EVEN input.
So where is the rest of your code then?

3. Originally Posted by Salem
So where is the rest of your code then?
Here's the one that works for ODD inputs...

Code:
```#include <iostream>

using namespace std;

void Left_Shift( int , int& , int* );

int main (void)
{
int N, sword_pos = 0 , ctr_var;
cin >> N;

int soldier[N], Num = N;

for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
soldier[ctr_var]=ctr_var+1;

for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
{
if ( sword_pos == N-1 )
sword_pos = -1;

Left_Shift( sword_pos + 1 , N , soldier );
sword_pos++;
}

cout<<endl<<soldier[0];
}

void Left_Shift ( int Who_To_Kill , int &N , int ARR[] )
{
for ( int i = Who_To_Kill ; i < N - 1 ; i++ )
{
ARR[i] = ARR[i+1];
}
N--;
}

// Compiled on Code::Blocks with GNU GCC Compiler```
How it works?

Code:
```// ODD NUMBER INPUT

N = 9

-1- 2 3 4 5 6 7 8 9
1 -3- 4 5 6 7 8 9
1 3 -5- 6 7 8 9
1 3 5 -7- 8 9
1 3 5 7 -9-
-3- 5 7 9
3 -7- 9
-3- 7
-3-

Survivor = 3

// EVEN NUMBER INPUT

N = 10

-1- 2 3 4 5 6 7 8 9 10
1 -3- 4 5 6 7 8 9 10
1 3 -5- 6 7 8 9 10
1 3 5 -7- 8 9 10
1 3 5 7 -9- 10
-1- 3 5 7 9
1 -5- 7 9
1 5 -9-
-5- 9
-5-

Survivor = 5```
Okay, so I realised that when I was working on a generalised program, I actually was messing around in the EVEN input code and I seem to have lost the original code that worked...
I'll have to write the code down again which I'll hopefully start and finish in a few hours after school. I'm not sharing the generalised program that I tried making (and failed) because, honestly, I don't like the way I've written it and I know of a certain flaw in the code.

I'll try doing it again after school with a fresh and calm mind as I got frustrated yesterday and came on here and asked the question anyway. I wouldn't mind having some help either way.

I read through the Wikipedia thing earlier this morning very briefly and its very interesting. I think it's a different approach to the problem than what I have tried but I wouldn't know unless I read through carefully (after school).... Thanks @Salem!

4. I replied to the @Salems message and it didn't get posted. Did I do something wrong?

5. Here's the one that works for ODD inputs:

Code:
```#include <iostream>

using namespace std;

void Left_Shift( int , int& , int* );

int main (void)
{
int N, sword_pos = 0 , ctr_var;
cin >> N;

int soldier[N], Num = N;

for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
soldier[ctr_var]=ctr_var+1;

for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
{
if ( sword_pos == N-1 )
sword_pos = -1;

Left_Shift( sword_pos + 1 , N , soldier );
sword_pos++;
}

cout<<endl<<soldier[0];
}

void Left_Shift ( int Who_To_Kill , int &N , int ARR[] )
{
for ( int i = Who_To_Kill ; i < N - 1 ; i++ )
{
ARR[i] = ARR[i+1];
}
N--;
}```
My logic:

Code:
```// ODD NUMBER INPUT

N = 9

-1- 2 3 4 5 6 7 8 9
1 -3- 4 5 6 7 8 9
1 3 -5- 6 7 8 9
1 3 5 -7- 8 9
1 3 5 7 -9-
-3- 5 7 9
3 -7- 9
-3- 7
-3-

Survivor = 3

// EVEN NUMBER INPUT

N = 10

-1- 2 3 4 5 6 7 8 9 10
1 -3- 4 5 6 7 8 9 10
1 3 -5- 6 7 8 9 10
1 3 5 -7- 8 9 10
1 3 5 7 -9- 10
-1- 3 5 7 9
1 -5- 7 9
1 5 -9-
-5- 9
-5-

Survivor = 5```
I went through the Wikipedia on the Josephus problem earlier this morning before school very briefly and I did find it interesting and I guess the logic is pretty different from my approach but I will never know until I go through carefully which I will in about 2 hours from now. Thanks Salem for the reference.

I realised that I was messing around on my EVEN input code to get a generalised program so I need to remake it for the time being but it's fairly similar to the ODD input one with different test cases.
I'm not adding my version of the generalised program as I don't think it's gonna be of much use as the logic is flawed and I'd be slightly embarrassed by it.

Also, I replied to @Salem earlier when I was at school but that message didn't show up here. Was there any issue in it?

6. Okay, I have no idea what's going on. I've replied twice and I don't see either of my messages here..... Did something go wrong? I did see them when I posted it but when I visited the page again, it wasn't there.

7. I'm gonna type again as a last try....

Here's my code that works for ODD inputs:

Code:
```#include <iostream>

using namespace std;

void Left_Shift( int , int& , int* );

int main (void)
{
int N, sword_pos = 0 , ctr_var;
cin >> N;

int soldier[N], Num = N;

for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
soldier[ctr_var]=ctr_var+1;

for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
{
if ( sword_pos == N-1 )
sword_pos = -1;

Left_Shift( sword_pos + 1 , N , soldier );
sword_pos++;
}

cout<<endl<<soldier[0];
}

void Left_Shift ( int Who_To_Kill , int &N , int ARR[] )
{
for ( int i = Who_To_Kill ; i < N - 1 ; i++ )
{
ARR[i] = ARR[i+1];
}
N--;
}```
My logic:

Code:
```/*// ODD NUMBER INPUT

N = 9

-1- 2 3 4 5 6 7 8 9
1 -3- 4 5 6 7 8 9
1 3 -5- 6 7 8 9
1 3 5 -7- 8 9
1 3 5 7 -9-
-3- 5 7 9
3 -7- 9
-3- 7
-3-

Survivor = 3

// EVEN NUMBER INPUT

N = 10

-1- 2 3 4 5 6 7 8 9 10
1 -3- 4 5 6 7 8 9 10
1 3 -5- 6 7 8 9 10
1 3 5 -7- 8 9 10
1 3 5 7 -9- 10
-1- 3 5 7 9
1 -5- 7 9
1 5 -9-
-5- 9
-5-

Survivor = 5```
I was at school when I first replied but the message didn't show up here when I looked again. @Salem I went through the Josephus problem on Wiki very briefly earlier this morning and I found it interesting as I believe it's a very different approach to the problem than mine but I wouldn't know unless I looked into it carefully which I will in about 2 hours from now.

I realised I was messing around on my EVEN input code for a generalised program and so I need to write it again to be able to post it here (I will in 2 hours). I'm not gonna be sharing my version of the generalised program because it's logic is flawed and I don't think it's gonna be of much use or help and I will be embarrassed slightly too :shy:

Thanks @Salem for the reference

8. Well, sometimes servers have little glitches...your post of 21 minutes ago appeared, to try again.

9. Your posts were in the moderation queue.
It should have told you something along those lines.

10. > This question is from HP Code Wars 2019 Bangalore.
There is a general theme to programming contests, and that is you sit down and think about the problem.

The first answer that comes into your head which involves "try every possible combination" is always the wrong approach. Occasionally you'll get lucky, but invariably you'll end up with either memory limit exceeded or time limit exceeded when the automated tests start throwing really large N values at your submission.

Remember, the problem as originally stated in mythology was N=40 and was meant to be a calculation you could do in your head in seconds.

Watch this for 10 minutes.