JAVA: Easiest solution O(logN) with explanation


  • 204
        public int lastRemaining(int n) {
            boolean left = true;
            int remaining = n;
            int step = 1;
            int head = 1;
            while (remaining > 1) {
                if (left || remaining % 2 ==1) {
                    head = head + step;
                }
                remaining = remaining / 2;
                step = step * 2;
                left = !left;
            }
            return head;
        }
    

    My idea is to update and record head in each turn. when the total number becomes 1, head is the only number left.

    When will head be updated?

    • if we move from left
    • if we move from right and the total remaining number % 2 == 1
      like 2 4 6 8 10, we move from 10, we will take out 10, 6 and 2, head is deleted and move to 4
      like 2 4 6 8 10 12, we move from 12, we will take out 12, 8, 4, head is still remaining 2

    then we find a rule to update our head.

    example:
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

    1. Let us start with head = 1, left = true, step = 1 (times 2 each turn), remaining = n(24)

    2. we first move from left, we definitely need to move head to next position. (head = head + step)
      So after first loop we will have:
      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 - > 2 4 6 8 10 12 14 16 18 20 22 24
      head = 2, left = false, step = 1 * 2 = 2, remaining = remaining / 2 = 12

    3. second loop, we move from right, in what situation we need to move head?
      only if the remaining % 2 == 1, in this case we have 12 % 2 == 0, we don't touch head.
      so after this second loop we will have:
      2 4 6 8 10 12 14 16 18 20 22 24 - > 2 6 10 14 18 22
      head = 2, left = true, step = 2 * 2 = 4, remaining = remaining / 2 = 6

    4. third loop, we move from left, move head to next position
      after third loop we will have:
      2 6 10 14 18 22 - > 6 14 22
      head = 6, left = false, step = 4 * 2 = 8, remaining = remaining / 2 = 3

    5. fourth loop, we move from right, NOTICE HERE:
      we have remaining(3) % 2 == 1, so we know we need to move head to next position
      after this loop, we will have
      6 14 22 - > 14
      head = 14, left = true, step = 8 * 2 = 16, remaining = remaining / 2 = 1

    6. while loop end, return head


  • 3
    C

    very clear answer, "long" but simple
    the 1-line answer really confuses me.


  • 0
    C

    Brilliant idea! Thanks a lot.


  • 0
    X

    This solution is awesome!!!! Thanks a lot!!!


  • 0

    This solution is super cool!


  • 0
    O

    The most clear answer I've ever seen! Although it's long but it really helps me on how to actually analysis and solve the problem. Thanks for the code and explanation!


  • 5

    excellent solution, here's some more thoughts that may help if you're still trying to figure this out.

    The last remaining value is any available remaining value until there is only 1 value left. We can start with 1 and always pick the smallest value remaining when our value gets eliminated.

    The problem becomes:

    • When do we eliminate our value?
      Our value is eliminated on a forward pass or if there are an odd number of elements.

    • How do we find the next value when our's is eliminated?
      This is probably the trickiest part of the solution. You will probably need to draw this out to see it but turns out if you start with 1 and double each iteration you'll be calculating the number of steps you'll need to take to reach the next available number.

    • How do we know when we only have 1 value remaining?
      Each iteration reduces the elements by half and in the case of odd that extra one is removed, so this becomes a simple size/2 integer division.


  • 0
    Q

    @NathanNi Awesome solution! Just curious, how much time did you spend on figuring out and writing this solution, please?


  • 0
    B

    @jdrogin Excellent observation and very well described. Thanks a lot.


  • 0
    I

    What a kickass idea you've got there mate!! Thanks for sharing :)


  • 0
    J

    Awesome!
    This is the iterative solution, more clear than the recursive solution.


  • 0
    B

    I also applied similar logic but my solution is a bit long though. When terms are odd, we end up deleting the head of the other end

        public int lastRemaining(int n) {
            if(n == 1){
                return 1;
            }
    
            int start = 2;
            int end = n % 2 == 0 ? n : n-1;
            int startStep =1;
            int endStep = 1;
            int terms = n/2;
            boolean directionLR = false;
            while(terms != 1){
                if(!directionLR){
                    end = end - (2 * endStep);
                    if(terms % 2 == 1){
                        start = start + (2 * startStep);
                    }
                }
                else{
                    start = start + (2 * startStep);
                    if(terms % 2 == 1){
                        end = end - (2 * endStep);
                    }
                }
                directionLR = !directionLR;
                endStep = endStep + endStep;
                startStep = startStep + startStep;
                terms = terms/2;
            }
            
            return end;
        }
    

  • 1
        public int lastRemaining(int n) {
          int head = 1, remain = n, step = 1;
          boolean left = true;
          while(remain > 1){
            if(left || remain % 2 == 1){
              head += step;    
            }  
            remain = remain/2;
            left = !left;
            step *= 2;
          }
          return head;
        }

  • 0
    S
    This post is deleted!

  • 0
    S

    Upvoted, thank you for sharing.

    So here is my attempt to understand this solution

    1. Each time loop gets traversed, "remaining" terms get halved.

    2. Each time loop gets traversed, "left" toggles between "True" and False

    3. Head may or may not be affected when traversed.
      3.1 head always gets update in two cases
      3.1.1. moving from left - easy to understand, first item always gets popped
      3.1.2. moving from right, if number of items "remaining" are odd - this needs a little understanding. To simplify visualization, assume elimination from right, happens from "left", so that the last item must be always eliminated. (Or think that "left" elimination - first item must always be eliminated, "right" elimination - "last" item must always be eliminated). Now the last item is either at "even" position or at "odd" position (after previous elimination). If the last item is at odd, then elimination must begin at first odd place(in the current configuration) - which is head. So head gets updated in this case.

    1. By what value should head be updated?
      4.1. It depends on "round number".
      4.2. In the first round, it will be updated by 1 (because step is 1) - 2^0
      4.3. In the second round, it will be updated (subject to point 3) by - 2^1
      4.4. In the kth round, it will be updated by - 2^k

    2. Reasoning behind step 4 -
      5.1. Again visualize that elimination is always from left with condition that "first" and "last" item must always be eliminated in alternating elimination round
      5.2. In the first step, all odd places are eliminated - (1) 2 (3) 4 (5) 6 (7) 8 (9) 10 (11) 12 (13) 14 (with at most 0 factor of 2)
      5.3. In the second round, all places with one factor of 2 gets eliminated -
      (2) 4 (6) 8 (10) 12 (14) (with at most 1 factor of 2)
      5.4. In the third round, all places with one factor of 4 gets eliminated -
      (4) 8 (12) (with at most 2 factors of 2)
      5.5. The reason behind this is each time number of remaining terms are getting halved, in the manner described above or considered alternatively round 1 eliminates table of 1 excluding all even, round 2 eliminates table of 2 excluding multiples of 4, round 3 eliminates table of 4 excluding multiples of 8, and so on.


  • 0
    Z

    @NathanNi
    I am positively sure that your solution works. However, I wonder how do you prove that when head = head + step will be valid, which means it has not been taken out of the array.

    Thanks, that is the only obscure point that I cannot quite explain for this problem.


  • 0
    C

    Really Amazing...


Log in to reply
 

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