C# O(logn) 55 ms


  • 0
    S

    The idea is to keep track of following 5 things:

    start: first number in the current sequence
    end: last number in the current sequence
    jump: jump between two consecutive numbers in the sequence
    elementsLeft: Number of elements left in the sequence
    fromLeft: this is the direction whether we are going from left to right or right to left.

    By using start, end and jump variables, you can easily construct the sequence (starting from start keep adding jump to the previously generated number in sequence till you hit end). The idea is to just keep track of these untill elementsLeft is 1.

    When you start eliminating from the left to right, your start will always become the next element in the sequence which you can simply construct by doing start + jump. The end will depend on the numbers left. if the total numbers left in the sequence are odd, then end will be the previous number in the sequence which is end - jump and if the numbers left are even; then end will stay same because you are removing all odd positions.

    When you start eliminating from right to left, your end will always become the previous element in the sequence and start will depend upon whether count of remaining numbers are even or odd. If even, start won't change, in case of odd, it will be the next number in sequence.

    public class Solution {
        public int LastRemaining(int n) {
            int start = 1;
            int end = n;
            int jump = 1;
            int elementsLeft = n;
            bool fromLeft = true;
            
            while (elementsLeft > 1){
                if (fromLeft){
                    start = jump + start;
                    if ((elementsLeft % 2) != 0){
                        end = end - jump;
                    }
                }else{
                    if ((elementsLeft % 2) != 0){
                        start = start + jump;
                    }
                    
                    end = end - jump;
                }
                
                jump = jump + jump;
                elementsLeft = elementsLeft / 2;
                fromLeft = !fromLeft;
            }
            
            return start;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.