×

# CDVA1604 - Editorial

Author: Suraj Prakash
Tester: Diwakar Bhardwaj
Editorialist: Suraj Prakash

Easy

# PROBLEM

Given a number n, find the person who survives when alternate person are killed standing in line.

## Explanation:

### IDEA 1:

The idea to solve the question using the Joseph game. Firstly all the odd numbers are killed and we are left with the problem of about half the size of the original size. Now, we can solve each smaller problem and get answer based on the answer of the smaller problem.

In the question, if there are n persons, then $c[n]$ denotes the survivor if we start the game from the first person, $d[n]$ denotes the survivor if there are n persons and we start the game from the second person.

### IDEA 2:

The given problem can be formulated using the given recurrence

$ans(1) = 1$
$ans(2) = 2$
$if (n$<$a(n-1)+2): a(n)=2$
$else: a(n) = a(n-1)+2$

# OPTIMAL COMPLEXITY:

$\mathcal{O}(N) + \mathcal{O}(Q)$

# AUTHOR'S SOLUTION:

Author's solution can be found here.
Tester's solution will be uploaded soon.

This question is marked "community wiki".

513
accept rate: 33%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×3,764
×947
×832
×34
×4

question asked: 30 Mar '16, 00:12

question was seen: 568 times

last updated: 30 Mar '16, 14:49