Why is the answer 2 ^ ( n — 1 ) ?
Why is the answer 2 ^ ( n — 1 ) ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Suppose the correct answer for f(n) = k and we want to find out f(n+1)
One could either place the highest number i.e. (n+1) either towards the rightmost end in the permutation or towards the leftmost end to satisfy constraints "maximum element between the indices [i..j] is either present at index i, or at index j" to satisfy for [1...n]. The other inner constraints would automatically be satisfied as we know f(n) is true. So there are 2 possible choices. f(n+1) = 2*f(n)
Now the base case n = 1. There is only 1 choice so f(1) = 1. Kind of Mathematical Induction Proof :P
So a recurrence relation f(n) = 2*f(n-1) when n > 1. Solving this recurrence f(n) = 2**n-1
I cannot understand why is f(n+1) = 2*f(n) ?
Emm. Suppose the ans for n = 3 has these possibilities:
4 possible answers
Now i need to find ans for n = 4. So _ _ _ _. I can either place it at 1st index or 4th index to satisfy the property "maximum element between the indices [i..j] is either present at index i, or at index j" for range [1..4]
So the ans will be:
4 + 4 = 8 possible answers
excuse me , why did you not count these possibles in your answer??
4 2 3 1
4 1 3 2
1 3 2 4
2 3 1 4 ???
4 2 3 1i=2,j=4 the maximum number is 3 which is neither in the ith nor in the jth position.
4 1 3 2i=2,j=41 3 2 4i=1,j=32 3 1 4i=1,j=3