Page Contents

**Arithmetic Slices Solution** Microsoft OA

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.

A subarray is a contiguous subsequence of the array.

**Example 1:**

Input:nums = [1,2,3,4]Output:3Explanation: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

*Also See: Amazon OA Online Assessment 2023 Questions and Answers*

**SOLUTION**

** Program: Arithmetic Slices Solution** in 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:***Arithmetic Slices Solution** in Python

- Create an array of size le (le=len(A))
**A**s 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**)**I**t 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: Arithmetic Slices Solution** in 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;
}
}
```

**Microsoft Online Assessment 2023 Questions List**

*Maximal Network Rank Solution**Min Deletions To Obtain String in Right Format**Day of week that is K days later Solution**Minimum Adjacent Swaps to Make Palindrome Solution**Lexicographically Smallest String**Longest Substring Without Two Contiguous Occurrences of Letter**String Without 3 Identical Consecutive Letters**Microsoft OA Longest Semi-Alternating Substring**Microsoft OA Min Steps to Make Piles Equal Height**Max Inserts to Obtain String Without 3 Consecutive ‘a’**Concatenated String Length with unique Characters**Largest K such that both K and -K exist in array**Microsoft OA Min Adj Swaps to Group Red Balls**Maximum Length of a Concatenated String with Unique Characters**Microsoft OA Unique Integers That Sum Up To 0**Find N Unique Integers Sum up to Zero**Microsoft OA Particle Velocity Solution**Microsoft OA Arithmetic Slices Solution**Microsoft OA Widest Path Without Trees Solution**Microsoft OA Jump Game Solution**Microsoft OA Fair Indexes Solution*