Google SWE Intern Interview Problem Solution With Explainations.

google

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👇

Comments

  1. Variable names are not explanatory at all. Please read the book Clean Code.

    ReplyDelete

Post a Comment

if you have any doubts let me know.