Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/390.html
You have a list arr
of all integers in the range [1, n]
sorted in a strictly increasing order. Apply the following algorithm on arr
:
- Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
- Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
- Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer n
, return the last number that remains in arr
.
Example 1:
Input: n = 9 Output: 6 Explanation: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] arr = [2, 4, 6, 8] arr = [2, 6] arr = [6]
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 109
Algorithm
It is very simple to do it with recursion. Use a bool type variable left2right
. True means to traverse from left to right, and false means to traverse from right to left.
When n is 1, it returns 1 no matter from left to right or from right to left.
If n is greater than 1,
- If it is from left to right, return twice the traversal of n/2 from right to left;
- If it is from right to left, it will be a little more troublesome. It is definitely necessary to call the recursive function on n/2, but it should be divided into parity.
- If n is an odd number, return twice the value of n/2 traversal from left to right;
- If n is an even number, double the traversal value of n/2 from left to right, and subtract 1
Code
-
public class Elimination_Game { public static void main(String[] args) { Elimination_Game out = new Elimination_Game(); Solution s = out.new Solution(); System.out.println(s.lastRemaining(9)); } class Solution { public int lastRemaining(int n) { return dfs(n, true); } int dfs(int n, boolean left2right) { if (n == 1) return 1; if (left2right) { return 2 * dfs(n / 2, false); } else { return 2 * dfs(n / 2, true) - 1 + n % 2; } } } class Solution2 { public int lastRemaining(int n) { return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2)); } } } ############ class Solution { public int lastRemaining(int n) { int a1 = 1, an = n, step = 1; for (int i = 0, cnt = n; cnt > 1; cnt >>= 1, step <<= 1, ++i) { if (i % 2 == 1) { an -= step; if (cnt % 2 == 1) { a1 += step; } } else { a1 += step; if (cnt % 2 == 1) { an -= step; } } } return a1; } }
-
class Solution: def lastRemaining(self, n: int) -> int: a1, an = 1, n i, step, cnt = 0, 1, n while cnt > 1: if i % 2: an -= step if cnt % 2: a1 += step else: a1 += step if cnt % 2: an -= step cnt >>= 1 step <<= 1 i += 1 return a1 ############ class Solution(object): def lastRemaining(self, n): """ :type n: int :rtype: int """ count = n head = 1 isFromLeft = True step = 1 while count > 1: if isFromLeft or count % 2 == 1: head = head + step count /= 2 step *= 2 isFromLeft = not isFromLeft return head
-
class Solution { public: int lastRemaining(int n) { int a1 = 1, an = n, step = 1; for (int i = 0, cnt = n; cnt > 1; cnt >>= 1, step <<= 1, ++i) { if (i % 2) { an -= step; if (cnt % 2) a1 += step; } else { a1 += step; if (cnt % 2) an -= step; } } return a1; } };
-
func lastRemaining(n int) int { a1, an, step := 1, n, 1 for i, cnt := 0, n; cnt > 1; cnt, step, i = cnt>>1, step<<1, i+1 { if i%2 == 1 { an -= step if cnt%2 == 1 { a1 += step } } else { a1 += step if cnt%2 == 1 { an -= step } } } return a1 }