Thursday, October 27, 2016

LeetCode OJ - Arithmetic Slices

Problem:

Please find the problem here.

Analysis:

It is possible for two arithmetic slices with different common difference to stick end to end, but not any closer, for example, we can have

1, 3, 5, 7, 4, 1

Therefore, we simply find the maximal length of the sequences with the same common difference, and then compute the count based on that.

Solution:

I claim that the consecutive sequence of $ k $ numbers with the same common difference contains $ \frac{(k - 1)(k - 2)}{2} $ arithmetic sequences. This is obviously true with $ k = 3 $. One can think of that as simply adding numbers as follow

Here is the set of all arithmetic slices with 3 numbers
1 2 3

Adding these two, here is the set of all arithmetic slices with 4 numbers. (Total 3 of them)
1 2 3 4
2 3 4

Adding these three, here is the set of all arithmetic slices with 5 numbers. (Total 6 of them)
1 2 3 4 5
2 3 4 5
3 4 5

Adding these four, here is the set of all arithmetic slices with 5 numbers. (Total 10 of them)
1 2 3 4 5 6
2 3 4 5 6
3 4 5 6
4 5 6

The pattern should be obvious by now.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/arithmetic-slices/

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

using namespace std;

namespace _LEET_ARITHMETIC_SLICES
{
    class Solution
    {
    public:
        int numberOfArithmeticSlices(vector<int>& A)
        {
            if (A.size() < 2)
            {
                return 0;
            }
            int s = 0;
            for (size_t i = 0; i < A.size() - 2; )
            {
                int d = A[i + 1] - A[i];
                size_t j = i + 2;
                while (j < A.size() && A[j] - A[j - 1] == d)
                {
                    j++;
                }
                int l = j - i;
                s += (l - 2) * (l - 1) / 2;
                i = j - 1;
            }
            return s;
        }
    };
};

using namespace _LEET_ARITHMETIC_SLICES;

int LEET_ARITHMETIC_SLICES()
{
    Solution solution;
    int case1Array[] = {1, 2, 3, 4};
    vector<int> case1(case1Array, case1Array + _countof(case1Array));
    cout << solution.numberOfArithmeticSlices(case1) << endl;
    return 0;
}

No comments :

Post a Comment