Arithmetic Slices Microsoft OA 2023

Arithmetic Slices Solution Microsoft OA 2023

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: 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

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))
• 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: 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