Given an input N where N is a number sequence from 1 to N.
say N= 6, so 1 2 3 4 5 6 is the sequence. In each iteration, odd position number gets eliminated until a single number is left.
E.g for sequence 1 2 3 4 5 6
After 1st iteration :2 4 6
After 2nd iteration : 4 , so no 4 is the winner.
Constraint: N>1
E.g: 1 2 3 4 5 6 7 8
2 4 6 8 after 1st iteration
4 8 after 2nd iteration
8 after 3rd iteration (winner)
Find the winner for the given N, where N can be a very large number.
Solution :
To solve this kind of problem we would go through the following steps :
1. Write multiple test cases and the respective output.
2. Analyze the output for the given input and the relation between them.
3. Once we find the relation we will try to express it in the form of mathematical expression if
possible.
4. Write the code/algorithm for the above expression.
5. Find the time and space complexity.
Test Cases
1. 1 2 3 4 5 6
2 4 6
4(winner)
2. 1 2 3 4
2 4
4
3. 1 2 3
2
4. 1 2 3 4 5 6 7 8
2 4 6 8
4 8
8
5. 1 2 3 4 5 6 7 8 9 10 11 12
2 4 6 8 10 12
4 8 12
8
6. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 4 6 8 10 12 14 16 18 20
4 8 12 16 20
8 16
16
So let's create a table for the given input N and its respective winner
Input N
|
winner
|
3
|
2
|
4
|
4
|
6
|
4
|
8
|
8
|
12
|
8
|
20
|
16
|
Before you all proceed further I would like you all to analyze the table and find the relationship between input and the winner.
Analyzed Relation:
the output is in 2^i format.
2^1
|
2
|
2^2
|
4
|
2^3
|
8
|
2^4
|
16
|
2^5
|
32
|
2^6
|
64
|
….
|
…..
|
Using the above table we can create the winner table for the range of inputs
Input Range
|
winner
|
2-3
|
2
|
4-7
|
4
|
8-15
|
8
|
16-31
|
16
|
32-63
|
32
|
….
|
….
|
Algorithm:
1. Initialize a variable say winner=2
2. Iterate while winner*2<=N
a. Multiply the variable winner by 2 and assign to the winner.
3.Return winner.
Code:
public long GetWinner(long input)
{
long winner=2;
while(winner*2<=n)
{
winner*=2;
}
return winner;
}
or we can also write using for loop
{
long winner;
for(winner=2;winner*2<=n;winner*=2);
return winner;
}
Time & Space Complexity:
Space Complexity: O(1) for the variable winner.
Time Complexity: log N, for average, worst and best case since we are increasing the loop by multiple of 2.
