C++ Three solutions: O(n), O(logn), O(1)


  • 2
    class Solution {
    public:
        int way1(int n) {
            int level = 1;
            for (long sum = 0; sum <= n; level++) 
                sum += level;
            return max(level - 2, 0);    
        }
        
        int way2(int n) {
            return sqrt(2 * (long)n + 1 / 4.0) - 1 / 2.0;
        }
        
        int arrangeCoins(int n) {
            long low = 1, high = n;
            while (low < high) {
                long mid = low + (high - low + 1) / 2;
                if ((mid + 1) * mid / 2.0 <= n) low = mid;
                else high = mid - 1;
            }
            return high;
        }
    };
    

  • 0
    D

    The first solution I think it is O(sqrt(n)). Correct me if I am wrong. Thx!


  • 0
    Z

    @DragonJ I think the author means O(k), O(1), O(log(k)), where k is the number of staircases. In fact k is of order O(log(n)), so technically you are correct.


  • 0
    W

    @Zach_Shi No. With n the author means, the number of coins, not the number of possible stairs.


  • 0
    W
    This post is deleted!

  • 0
    W

    @DragonJ Yes, you are correct.


  • 0
    long mid = low + (high - low + 1) / 2;
    

    Why do we need the + 1 here, without +1, we will get Time Exceed Limit. Can anyone help me understand the corner case about that?
    I assume there is something related to the stopping condition while (low < high)


Log in to reply
 

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