C# - iterative log(n) clean with thoughts explained.


  • 0

    For me the key to understanding this solution was realizing that 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.

        public int LastRemaining(int n) 
        {
           int count = n;
           int val = 1;
           int step = 1;
           bool forward = true;
           
           while (count > 1)
           {
               if (forward || count % 2 == 1)
               {
                   val += step;
               }
               step *= 2;
               count /= 2;
               forward = !forward;
           }
           
           return val;
        }
    

Log in to reply
 

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