Contents

**Particle Velocity Solution Microsoft OA**

You are a programmer in a scientific team doing research into particles. As an experiment, you have measured the position of a single particle in N equally distributed moments of time. The measurement made in moment K is recorded in an array particles as particles[K]. Now, your job is to count all the periods of time when the movement of the particle was stable. Those are the periods during which the particle doesn’t change its velocity: i.e. the difference between any two consecutive position measurements remains the same. Note that you need at least three measurements to be sure that the particle didn’t change its velocity.

**For Example**

- 1, 3, 5, 7, 9 is stable (velocity is 2)
- 7, 7, 7, 7 is stable (particle stays in place)
- 3, -1, -5, -9 is stable (velocity is 4)
- 0, 1 is not stable (you need at least three measurements)
- 1, 1, 2, 5, 7 is not stable (velocity changes between measurements)

More formally, your task is to find all the periods of time particles[P], particles[P+1], ….particles[Q] (of length at least 3) during which the movement of the particle is stable. Note that some periods of time might be contained in others (see below example).

**Example:**

Input: [-1, 1, 3, 3, 3, 2, 3, 2, 1, 0]

Output: 5

**Explanation:**

Possible periods of time for which velocity is stable are:

values | location(from, to) | Velocity |
---|---|---|

`[-1, 1, 3]` | (0,2) | 2 |

`[3, 3, 3]` | (2,4) | 0 |

`[3, 2, 1, 0]` | (6,9) | -1 |

`[3, 2, 1]` | (6,8) | -1 |

`[2, 1, 0]` | (7,9) | -1 |

**Note:** Last two periods are contained by `(6,9)`

**Write a function:**

`public static int particleVelocity(int[] particles)`

that given array `particles`

consisting of `N`

integers representing the results of the measurements, returns the number of periods of time when the movement of the particle was stable. The function should return `-1`

if the result exceeds `10^9`

.

**More examples:**

**Example 1:**

Input: `[1, 3, 5, 7, 9]`

Output: `6`

*Explanation:*

Possible periods of time for which velocity is stable are:

values | location(from, to) | Velocity |
---|---|---|

`[1, 3, 5]` | (0,2) | 2 |

`[3, 5, 7]` | (1,3) | 2 |

`[5, 7, 9]` | (2,4) | 2 |

`[1, 3, 5, 7, 9]` | (0,4) | 2 |

`[1, 3, 5, 7]` | (0,3) | 2 |

`[3, 5, 7, 9]` | (1,4) | 2 |

**Example 2:**

Input: `[7, 7, 7, 7]`

Output: `3`

*Explanation:*

Possible periods of time for which velocity is stable are:

values | location(from, to) | Velocity |
---|---|---|

`[7, 7, 7, 7]` | (0,3) | 0 |

`[7, 7, 7]` | (1,3) | 0 |

`[7, 7, 7]` | (0,2) | 0 |

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

**SOLUTION**

*Program:**Particle Velocity Solution in C++*

**Explanation:**

The simple formula : ans = ans + (streak * (streak + 1) / 2) – (2 * streak – 1) is nothing but the count of all subarrays for the given streak minus the count of subarrays of length 1 and 2.

Suppose we have an array of size n.

Total number of subarrays of the array : n * (n + 1) / 2

Count of subarrays of length 1 : n

Count of subarrays of length 2 : n – 1

Therefore, count of subarray of length ≥ 3 : (n * (n + 1) / 2) – (n – n – 1) = (n * (n + 1) / 2) – (2 * n – 1)

```
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums)
{
int ans = 0;
for(int i = 0 ; i < nums.size() ; )
{
int streak = 0, cd = INT_MAX;
if(i < nums.size() - 1)
{
streak = 2;
cd = nums[i] - nums[i + 1];
}
i++;
while(i < nums.size() - 1 and nums[i] - nums[i + 1] == cd)
{
streak++;
i++;
}
if(streak >= 3)
ans = ans + (streak * (streak + 1) / 2) - (2 * streak - 1);
}
return ans;
}
};
```

*Program:**Particle Velocity Solution in Python*

**Explanation:**

nums = [1, 3, 5, 7, 9, 13]

differ = [2, 2, 2, 2, 4]

In order to match the condition – at least three elements, there are must have more than 2 continuous and same value elements in the differ for calculate arithmetic slices.

This problem is converted to calculate the number of combinations in differ’s sublist [2, 2, 2, 2] and [4]. (see function def arithmetic)

[2, 2, 2, 2] -> n_same = 4

kernal = 2, (include 3 elements)

num(n_same, k=2) = 3 ((0,1), (1, 2), (2, 3))

kernal = 3,

num(n_same, k=3) = 2 ((0,2), (1, 3))

kernal = 4,

num(n_same, k=4) = 1 ((0,3))

Total = 6

```
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
if len(nums) <= 2:
return 0
# n_same is number of continuous elements with same value
# (in difference space)
result, n_same = 0, 1
for i in range(1, len(nums)-1):
diff_1 = nums[i] - nums[i-1]
diff_2 = nums[i+1] - nums[i]
if diff_1 == diff_2:
n_same += 1
else:
result += self.arithmetic(n_same)
n_same = 1
result += self.arithmetic(n_same)
return result
def arithmetic(self, n):
"""
Sum(
num(n, k=2), num(n, k=3), ...,num(n, k=n)
)
if n = [1, 1, 1],
num(n, k=2) = 2 ((0, 1) and (1, 2));
num(n, k=3) = 1 ((0, 2)).
"""
# Set kernal = 2 to match the condition: at least three elements
kernal = 2
if n < kernal:
return 0
# Trapezoidal rule
return int(((n - kernal + 1) + (1)) * (n - kernal + 1) / 2)
### Same as:
# num_arith = 0
# while kernal <= n:
# num_arith += (n - kernal + 1)
# kernal += 1
# return num_arith
```

*Program:*** Particle Velocity Solution** in Java

```
class Solution {
/**
* count length of the maximum size Arithmetic progression that can be made from given index.
* nums = [1,2,3,4,5,8,11]
* ap = [5,4,3,2,3,2,1]
* because the array need to continuous , so starting from given number iterate over all the next number, the number would be either included in AP or not.
* If number is not included then it mark the end of the AP.
* In this way calculate the length of the AP foe each index.
* So given a AP of size 5 like 1,2,3,4,5 we can make ap[i] - 2 sub arrays of length greater than 3. AP size should be equal to and greater than 3
* Do the sum for all the number to get all possible sub arrays
* Time Complextiy : O(N^2)
*/
public int numberOfArithmeticSlices(int[] nums) {
int n = nums.length;
int[] ap = new int[n];
int last;
int d = Integer.MIN_VALUE;
boolean init;
for (int i = 0; i < n; i++) {
int count = 1;
init = false;
for (int j = i + 1; j < n; j++) {
if (!init) {
d = nums[j] - nums[j - 1];
init = true;
count++;
} else if (nums[j] - nums[j - 1] == d) {
count++;
} else {
break;
}
}
ap[i] = count;
}
int sum = 0;
for (int i = 0; i < n; i++) {
if (ap[i] >= 3) {
sum = sum + (ap[i] - 2);
}
}
return sum;
}
}
```

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