Problem Statement:
This problem involves calculating the sum of all subarrays that are in Arithmetic Progression (AP) with a common difference of either
0
or 1
. Additionally, each array element is considered to be an AP with a single element. Key Concepts:
Arithmetic Progression (AP): A sequence is in AP if the difference between consecutive elements is constant.
- Difference
0
: All elements are the same. - Difference
1
: Elements increase by1
sequentially.
- Difference
Subarrays: Continuous parts of the array. For example, for
[1, 2, 3]
, the subarrays are:[1], [2], [3], [1, 2], [2, 3], [1, 2, 3]
Goal: Calculate the sum of all elements in all subarrays that follow an AP with a difference of
0
or1
.
Approach:
Calculate Total Sum (
w
):- Compute the sum of all array elements to adjust for overcounting later.
Handle Subarrays with Difference
1
:- Traverse the array.
- For each valid AP subarray (difference
1
), extend it and update the cumulative sum of valid subarrays ending at each index.
Handle Subarrays with Difference
0
:- Similar to the previous step, but consider AP subarrays with a difference of
0
.
- Similar to the previous step, but consider AP subarrays with a difference of
Adjust for Overcounting:
- Subtract the total array sum (
w
) to avoid double-counting single elements.
- Subtract the total array sum (
Return Final Result:
- The sum of all subarrays in AP with differences
0
or1
.
Code:
package hashing;
import java.util.Scanner;
public class SumofAllSubarraysinAP {
public static int sumsubarrays(int [] b,int n) {
int w = 0; // sum of all array elements
for (int i = 1; i <= n; ++i) {
w += b[i];
}
int v = 0;
int c = 0;
int prv = 0;
int answer = 0;
for (int i = 1; i <= n; ++i) {
if (i == 1) {
v = v + b[i];
prv = b[i];
} else {
if (b[i] - b[i - 1] == 1) {
c = c + 1;
v = prv + b[i] * (c + 1);
prv = v;
} else {
v = b[i];
c = 0;
prv = b[i];
}
}
answer = answer + v; // sum of all valid subarrays ending at index i
}
// Reset variables for the second loop
v = 0;
c = 0;
prv = 0;
for (int i = 1; i <= n; ++i) {
if (i == 1) {
v = v + b[i];
prv = b[i];
} else {
if (b[i] - b[i - 1] == 0) {
c = c + 1;
v = prv + b[i] * (c + 1);
prv = v;
} else {
v = b[i];
c = 0;
prv = b[i];
}
}
answer = answer + v; // sum of all valid subarrays ending at index i
}
answer = answer - w;
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int [] arr=new int[n+1];
int i=1;
while(i<=n) {
arr[i]=sc.nextInt();
i++;
}
System.out.println(sumsubarrays(arr,n));
sc.close();
}
}
Thanks for reading the blog.Hope you like it..
If you have any doubt comment down below👇
Variable names are not explanatory at all. Please read the book Clean Code.
ReplyDeleteOK I will try my best
Delete