Help me understand this part. Which two pointer pattern is this? Where to learn more topics like this?
for (int i = 1, j = 1; i <= n; i = j) {
for (j = i + 1; j <= n and a[i] == a[j]; j++);
int k = (j - i);
ans -= 1LL * k * (k + 1) / 2;
}
Counting the number of subarrays which have the same elements is pretty easy. Let r be the rightmost index such that a[l] = a[l + 1] = ... = a[r] . Then the number of subarrays having the same elements will be $$$\frac{(r - l + 1) \cdot (r - l + 2)}{2}$$$. Do similar thing for other elements too. Check out the code to understand better.
Correct answer in sample case. But I get wrong answer in [1,2,3] answer = 2 how to fix this?
Problem E Sub-Array
An array is Beautiful if all the elements in that array are identical.
You are given an array A consists of N integers. Now for the given array, you have to find the number of non-empty subarrays which are not Beautiful.
A subarray is a contiguous part of the array.
Example: A = [ 1, 0, 1, 0 ] where N = 4 Possible six subarrays which aren’t beautiful. [1,0] , [1,0,1] , [1,0,1,0] , [0,1] , [0,1,0] , [1,0]
Input Input starts with an integer T denoting the number of test cases. Each case starts with an T integer N denoting the number of integers in the array. Next line will contain N integers of array A, separated by spaces.
Output For each case, print the case number and the result in a single line.
Constraints: ● 1 ≤ T ≤ 10 ● 1 ≤ N ≤ 10^5 ● 0 ≤ A[i] ≤ 2^31-1
Sample Input
2
4
1 0 1 0
7
1 1 2 3 3 4 7
Output for Sample Input
Case 1: 6
Case 2: 19
Update: Give me a hint please
