Leetcode-441 Arranging Coins

#441.   Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.
超时：忘了看题目条件。超时。

class Solution {
public:
    int arrangeCoins(int n) {
        
        int i=0;
        while(true)
        {
            if(i*(i+1)/2<=n)
                i++;
            else
                break;
        }
        return i-1;
    }
};

然后就想空间换时间，变成下面这样：

class Solution {
public:
    int arrangeCoins(int n) {
        int size=pow(2,16);
        int nums[size];
        nums[1]=1;
        for(int i=2;i<size;i++)
        {
            nums[i]=nums[i-1]+i;
        }
        int j;
        for(j=1;j<size;j++)
        {
            if(nums[j]>n)
                break;
        }
        return j-1;
        
    }
};

发现效率差了点，虽然过是能过。不甘心啊。