PROBLEM LINK: Cook with Chef
Author: Jeevansh Gagroo
Tester: Tanay Morakhia
Editorialist: Jeevansh Gagroo
DIFFICULTY
Easy
PREREQUISITES
Knowledge of General Mathematics, Basic Programming
EXPLANATION
Some Observations:
- We are given the integer L, and with the help of L we create a new number 2L=NUM (That is the number of chefs participating).
- NUM is now some power of 2 and therefore even. This signifies that in each and every test case there will be only one winner as the number of chefs becomes even.
- Now the chefs will compete in adjacent pairs. This means in each iteration, there will be half of the original chefs left.
- The winners from adjacent pairs become the new pair and so on.
- Finally we will be left with only one winner (as no 2 chefs have the same number of ingredients).
For Example: L=2. which means the number of chefs (NUM=2L=4). Therefore the number of ingredients with each chef is {1, 2, 3, 4 } respectively. Here we add 1+2=3 which is an odd number therefore Chef 1 wins as he has lower index (or less ingredients). The next pair is 3 and 4 which results in 7 again which is odd so, Chef 3 wins as he has a lower index. Now both the winners from each pair becomes another pair. And now we add 1 and 3 = 4. Now 4 is even so the chef with higher index wins. That being 3. And now Chef 3 is the last one standing so Chef 3 is the winner.
Hence 3 is printed.
For better explanation refer: Explanation
SOLUTION
C++ Solution: Cook with Chef C++ Solution
Python Solution: Cook with Chef Python Solution
Java Solution: Cook with Chef Java Solution