Google SWE Intern Interview Problem Solution With Explainations.

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:

1. 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 by 1 sequentially.

2. 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]

3. Goal: Calculate the sum of all elements in all subarrays that follow an AP with a difference of 0 or 1.

Approach:

1. Calculate Total Sum (w):

   • Compute the sum of all array elements to adjust for overcounting later.

2. 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.

3. Handle Subarrays with Difference 0:

   • Similar to the previous step, but consider AP subarrays with a difference of 0.

4. Adjust for Overcounting:

   • Subtract the total array sum (w) to avoid double-counting single elements.

5. Return Final Result:

• The sum of all subarrays in AP with differences 0 or 1.

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👇