Saturday, November 5, 2016

LeetCode OJ - Arranging Coins

Problem:

Please find the problem here.

Analysis:

The stair case of $ k $ layer has $ \frac{k(k+1)}{2} $ coins.
The goal is to find $k $ such that $ \frac{k(k+1)}{2} \le n < \frac{(k+1)(k+2)}{2} $.

Solving this equation directly is not easy, but ...

Solution: 

We can use binary search. Imagine there is an array $ [0, \cdots, n ] $ with entries $ \frac{k(k+1)}{2} $. All we need to do is to find the largest element smaller than $ n $. We do not need to actually have the array, because we can compute the value on the fly! Extra care is paid to make sure we do not overflow by dividing first.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/arranging-coins/

#include "LEET_ARRANGING_COINS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_ARRANGING_COINS
{
    class Solution {
    public:
        int arrangeCoins(int n)
        {
            if (n == 0)
            {
                return 0;
            }
            if (n == 1)
            {
                return 1;
            }
            long long l = 0;
            long long u = n;
            while (u - l > 1)
            {
                long long m = (l + u) / 2;
                long long d = 0;
                if (m % 2 == 0)
                {
                    d = (m + 1) * (m / 2);
                }
                else
                {
                    d = ((m + 1) / 2) * m;
                }
                if (d > n)
                {
                    u = m;
                }
                else
                {
                    l = m;
                }
            }
            return l;
        }
    };
};

using namespace _LEET_ARRANGING_COINS;

int LEET_ARRANGING_COINS()
{
    Solution solution;
    for (int i = 0; i <= 10; i++)
    {
        cout << i << " " << solution.arrangeCoins(i) << endl;
    }
    cout << solution.arrangeCoins(119) << endl;
    cout << solution.arrangeCoins(120) << endl;
    cout << solution.arrangeCoins(121) << endl;
    cout << solution.arrangeCoins(~(1<<31)) << endl;
    return 0;
}

No comments :

Post a Comment