Problem 2? How'd people approach it?


  • 0

    I spent a long long time trying to see if there was some kind of pattern to follow, but I just couldn't seem to find anything concrete. Really curious how people approached it - I tried brute forcing it, and had an O(n) solution, but that TLE and too much memory. Was there some kind of trick that I was missing??


  • 1
    B

    the complexity could be O(logn)
    use two indices to record the edge of unexplored numbers.
    and use a counter to record the number of visited numbers.

    the trick is you do not need to actually visit each number, you can find the number of numbers you would visit in certain pass by
    (right-left)/step + 1

    class Solution {
    public:
        int lastRemaining(int n) 
        {
            int count = 0, step = 2, left = 1, right = n;
            while(count < n)
            {
                if(count==n-1) return right;
                count += (right-left)/step+1;
                if((right-left)%step==0) right -= step/2;
                left += step/2;
                if(count==n-1) return left;
                step *= 2;            
    
                count += (right-left)/step+1;
                if((right-left)%step==0) left += step/2;
                right -= step/2;
                if(count==n-1) return right;
                step *= 2;            
            }
            return left;
        }
    };

  • 0
    C

    A pattern can be easily found if we do every elimination from left: the remaining numbers can only be powers of 2. For one elimination from right and the length of current array is not odd (otherwise it will be equivalent to elimination from left), the pattern is still there, only with some shift.

    class Solution {
    public:
    	int lastRemaining(int n) {
    		if (n < 1) return 0;
    		if (n == 1) return 1;
    		int mul = 1, shift = 0;
    		while (n != 1)
    		{
    			n /= 2;
    			mul *= 2;
    			if (n == 1) break;
    			if ((n & 1) == 0)
    				shift -= mul;
    			n /= 2;
    			mul *= 2;
    		}
    		return mul + shift;
    	}
    };

  • 3
    C

    Here's my recursive solution

    • If eliminate from left
      [1...2n+1] -> [2,4,6,...2n] = 2 * [1...n]
      [1...2n+0] -> [2,4,6,...2n] = 2 * [1...n]
    • If eliminate from right
      [1...2n+1] -> [2,4,6,...,2n] = 2 * [1...n]
      [1...2n+0] -> [1,3,5,...,2n-1] = 2 * [1...n] - 1
    class Solution {
    public:
        int lastRemaining(int n, bool fromLeft) {
            if(n <= 1) {
                return 1;
            }
            if(fromLeft) {
                return 2 * lastRemaining(n / 2, false);
            } else {
                if(n & 1) {
                    return 2 * lastRemaining(n / 2, true);
                } else {
                    return 2 * lastRemaining(n / 2, true) - 1;
                }
            }
        }
    
        int lastRemaining(int n) {
            return lastRemaining(n, true);
        }
    };
    

  • 0
    W

    We only need the left, right and step to decide the left, right and step of the next iteration:

    class Solution {
    public:
        int lastRemaining(int n) {
            int left = 1;
            int right = n;
            int t = 1;
            while (right > left) {
                if (((right - left) / t) % 2 == 0)
                    right -= t;
                left  += t;
                t *= 2;
    
                if (left >= right)
                    return left;
    
                if (((right - left) / t) % 2 == 0)
                    left += t;
                right -= t;
                
                t *= 2;
            }
            return left;
        }
    };

  • 0

    I got TLE too, even though I was thinking “What on earth am I doing” when clicking the Submit button. Really, it was pretty obvious that I only get penalty time this way. Must be because it was 4:30 a. m. here.

    Then I found a pretty elegant solution. At first, we remove all odd numbers, so the resulting sequence can be expressed as 2k + 2 where k = 0, 1, 2... Generalizing that, I figure that it must be a * k + b after every iteration, where a and b are some integers. The trick is, then, to update those a and b on each iteration. Note that b is the first number in the sequence.

    If we're going left-to-right, then b increases by a. That's because we're striking out the first number (with k == 0), so the first remaining one will be a * 1 + b.

    If we're going right-to-left, then b only increases by a if we end up striking out the first (the last from the right) number. That happens only if the number of numbers is odd. Otherwise b is unchanged.

    As for a, it just doubles on every iteration. It's that simple. The total number of numbers just halves (round down).

    That gave me a very simple algorithm:

    1. Initialize a = 1, b = 1.
    2. While there are more than one number remaining repeat the following:
    3. If going left-to-right or if the number of remaining numbers is odd, increase b by a.
    4. Double a.
    5. Half the number of numbers.
    6. Reverse the direction and repeat.
    7. When the loop is over, return b.

    The code in Java:

        public int lastRemaining(int n) {
            int a = 1, b = 1; // 1k + 1
            int m = n;
            boolean ltr = true;
            while (m > 1) {
                if (ltr || (m & 1) == 1) {
                    b += a;
                }
                a *= 2;
                m /= 2;
                ltr = !ltr;
            }
            return b;
        }
    

  • 0
    E

    As long as you use array,map,set, and loop it, you always get TLE. After I spent about 1.5 hours and tried two array ways and met TLE. I decided to try number calculate then find a solution soon.


  • 0
    D

    The trick is that we don't need to store everything in the middle. Storing the step is enough as everything in the middle will be left + step * k. From the left, right and the step, we can calculate them in the next iteration.


Log in to reply
 

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