Microsoft OA Arithmetic Slices Solution

Microsoft OA Arithmetic Slices Solution

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

  • For example, [1,3,5,7,9][7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.

Given an integer array nums, return the number of arithmetic subarrays of nums.

subarray is a contiguous subsequence of the array.

Also See: Microsoft Online Assessment Questions and Solution

Example 1:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

Input: nums = [1]
Output: 0

Constraints:

  • 1 <= nums.length <= 5000
  • -1000 <= nums[i] <= 1000

Solution:

Program C++:

Key points:

  • Just keep looking for continuous sequence and get its length.
  • For a sequence of n gaps, it generates n-1 3-item combo, n-2 4-item combo, n-3 5-item combo and go on till 1 combo with all items in sequence. The total combination count is simply n*(n-1)/2.
  • Once a sequence is over, add up the slice count and keep going.
  • Remember to add when last item is scanned.
  • You can use item count start from 2 instead of gap count start from 1, same result for sure.
 int numberOfArithmeticSlices(const vector<int>& A) {
    int len = A.size();
    if (len < 3)
      return 0;
    int ret = 0;
    int prevDiff = A[1]-A[0];
    int seqLen = 1;
    for (int i=2; i<len; ++i) {
      if (A[i] - A[i-1] == prevDiff)
        ++seqLen;
      else {
        ret += (seqLen-1)*seqLen/2;
        seqLen = 1;
        prevDiff = A[i] - A[i-1];
      }
    }
    ret += (seqLen-1)*seqLen/2;
    return ret;
  }

Program Python:

Microsoft OA Arithmetic Slices Solution
Microsoft OA Arithmetic Slices Solution
  • Create an array of size le (le=len(A))
  • As given ”A sequence of numbers is called arithmetic if it consists of at least three elements”, start for loop from 2 to le.(because first two elements(index 0 and 1) will never from a sequence as minimum length of a sequence is 3)
  • It is also given that ”A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
    here i is current element ,if A[i]-A[i-1] == A[i-1]-A[i-2] then sequence length for current element i.e l[i] will be 1+sequence length of previous element(l[i-1)

To return the total number of arithmetic slices in the array A return Caluculated Sum of array l.

class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        le=len(A)
        l=[0]*(le)
        for i in range(2,le):
            if A[i]-A[i-1] == A[i-1]-A[i-2]:
                l[i]=1+l[i-1]
        return sum(l)

Program Java:

Explanation:
We need to find the consecutive subarray, if its length is len, then it could contribute (len – 1) * (len – 2) / 2 slices,
then start from the end of last consecutive +1, and go ahead to find the next consecutive util the end of array.

// AC: Runtime: 0 ms, faster than 100.00% of Java online submissions for Arithmetic Slices.
// Memory Usage: 36.7 MB, less than 80.00% of Java online submissions for Arithmetic Slices.
// thoughts: find the consecutive subarray, then it could contribute (len - 1) * (len - 2) / 2 slices, 
//        then start from the end of last consecutive +1, and go ahead to find the next consecutive.
// T:O(n), S:O(1)
// 
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int size = nums.length, ret = 0;
        if (size >= 3) {
            for (int i = 0; i < size - 2;) {
                int diff1 = nums[i + 1] - nums[i], diff2 = nums[i + 2] - nums[i + 1];
                if (diff1 == diff2) {
                    int end = i + 2;
                    while (end < size && nums[end] - nums[end - 1] == diff1) {
                        end++;
                    }
                    // length of the consecutive subarray that has same adjacent diff.
                    int len = end - i;
                    // may produce such amount amount of `arithmetic slices`.
                    ret += (len - 1) * (len - 2) / 2;
                    
                    // forwarding to the sequence's end + 1
                    i = end - 2;
                } else {
                    i++;
                }
            }
        }

        return ret;
    }
}

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions

Leave a Comment