Given two sorted arrays A and B of size N and M respectively, the task is to find the value V, which is the summation of (A[j] – A[i]) for all pairs of i and j such that (j – i) is present in array B.
Examples:
Input: N = 4, M = 2, A[] = {1, 2, 3, 4}, B[] = {1, 3}
Output: 6
Explanation: Valid pairs of (i, j) are (1, 2), (2, 3), (3, 4), (1, 4). So the answer will be 2 – 1 + 3 – 2 + 4 – 3 + 4 – 1 = 6Input: N = 3, M = 3, A[] = (2, 3, 5}, B[] = (1, 2, 3}
Output: 6
Approach: To solve the problem follow the below steps:
- Let’s find the answer for one value in the B array. Later we can sum it up to get the end result.
- Suppose there is a value ‘x’ in the B array. So the result will be equal to
- result = (A[x] – A[0]) + (A[x+1] – A[1]) + (A[x+2] – A[2]) ……. and so on till the end of the array.
- If we re-arrange the equation, then we will get something like this:
- result = (A[x] + A[x+1] + A[x+2] + …. + A[n-1]) – (A[0] + A[1] + A[2] + ……..A[n-x-1]).
- Which is nothing but the suffix sum of the last x elements – prefix sum of the first n-x-1 elements.
- Which will now yield the value of the single element in the array B. Now we iterate over the array B and compute the summation of all the results to get the end result.
Below are the steps to solve the above approach:
- Declare and initialize prefix sum and suffix sum arrays with zeroes.
- Compute prefix sum and suffix sum.
- Iterate over array B. Find out the summation of the suffix sum of the last B[i] elements – prefix sum of the first N-B[i]-1 elements for all the elements in array B.
- Print the result.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function that computes the final answerint ScoreOfSortedArray(int A[], int B[], int N, int M){ // Initialing prefixsum and // suffixsum arrays. int sufSum[N] = { 0 }; int preSum[N] = { 0 }; // computing suffix suum array. sufSum[N - 1] = A[N - 1]; for (int i = N - 2; i >= 0; i--) { sufSum[i] = sufSum[i + 1] + A[i]; } // Computing prefix suum array. preSum[0] = A[0]; for (int i = 1; i < N; i++) { preSum[i] = preSum[i - 1] + A[i]; } int res = 0; for (int i = 0; i < M; i++) { // Adding suffix sum of last B[i] // elements. Subtracting prefix // sum of first N-B[i]-1 elements. res += sufSum[B[i]]; res -= preSum[N - B[i] - 1]; } return res;}// Drivers codeint main(){ int N = 4, M = 2; int A[] = { 1, 2, 3, 4 }; int B[] = { 1, 3 }; // Function call cout << ScoreOfSortedArray(A, B, N, M); return 0;} |
Java
// Java code for the above approachclass GFG { // Function that computes the final answer static int scoreOfSortedArray(int[] A, int[] B, int N, int M) { // Initializing prefix sum and suffix sum arrays int[] sufSum = new int[N]; int[] preSum = new int[N]; // Computing suffix sum array sufSum[N - 1] = A[N - 1]; for (int i = N - 2; i >= 0; i--) { sufSum[i] = sufSum[i + 1] + A[i]; } // Computing prefix sum array preSum[0] = A[0]; for (int i = 1; i < N; i++) { preSum[i] = preSum[i - 1] + A[i]; } int res = 0; for (int i = 0; i < M; i++) { // Adding suffix sum of last B[i] elements // Subtracting prefix sum of first N-B[i]-1 // elements res += sufSum[B[i]]; res -= preSum[N - B[i] - 1]; } return res; } // Driver code public static void main(String[] args) { int N = 4, M = 2; int[] A = { 1, 2, 3, 4 }; int[] B = { 1, 3 }; // Function call System.out.println(scoreOfSortedArray(A, B, N, M)); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python code for the above approachdef score_of_sorted_array(A, B, N, M): # Initializing suffix sum and prefix sum arrays sufSum = [0] * N preSum = [0] * N # Computing suffix sum array sufSum[N - 1] = A[N - 1] for i in range(N - 2, -1, -1): sufSum[i] = sufSum[i + 1] + A[i] # Computing prefix sum array preSum[0] = A[0] for i in range(1, N): preSum[i] = preSum[i - 1] + A[i] res = 0 for i in range(M): # Adding suffix sum of last B[i] elements res += sufSum[B[i]] # Subtracting prefix sum of first N-B[i]-1 elements res -= preSum[N - B[i] - 1] return res# Driver codeN = 4M = 2A = [1, 2, 3, 4]B = [1, 3]# Function callprint(score_of_sorted_array(A, B, N, M)) |
C#
// C# code for the above approachusing System;public class GFG { // Function that computes the final answer static int ScoreOfSortedArray(int[] A, int[] B, int N, int M) { // Initializing prefixsum and suffixsum arrays. int[] sufSum = new int[N]; int[] preSum = new int[N]; // Computing suffix sum array. sufSum[N - 1] = A[N - 1]; for (int i = N - 2; i >= 0; i--) { sufSum[i] = sufSum[i + 1] + A[i]; } // Computing prefix sum array. preSum[0] = A[0]; for (int i = 1; i < N; i++) { preSum[i] = preSum[i - 1] + A[i]; } int res = 0; for (int i = 0; i < M; i++) { // Adding suffix sum of last B[i] elements. // Subtracting prefix sum of first N-B[i]-1 // elements. res += sufSum[B[i]]; res -= preSum[N - B[i] - 1]; } return res; } // Driver code static void Main(string[] args) { int N = 4, M = 2; int[] A = { 1, 2, 3, 4 }; int[] B = { 1, 3 }; // Function call Console.WriteLine(ScoreOfSortedArray(A, B, N, M)); }}// This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for the above approachfunction score_of_sorted_array(A, B, N, M) { // Initializing suffix sum and prefix sum arrays let sufSum = new Array(N).fill(0); let preSum = new Array(N).fill(0); // Computing suffix sum array sufSum[N - 1] = A[N - 1]; for (let i = N - 2; i >= 0; i--) { sufSum[i] = sufSum[i + 1] + A[i]; } // Computing prefix sum array preSum[0] = A[0]; for (let i = 1; i < N; i++) { preSum[i] = preSum[i - 1] + A[i]; } let res = 0; for (let i = 0; i < M; i++) { // Adding suffix sum of last B[i] elements res += sufSum[B[i]]; // Subtracting prefix sum of first N-B[i]-1 elements res -= preSum[N - B[i] - 1]; } return res;}// Driver codelet N = 4;let M = 2;let A = [1, 2, 3, 4];let B = [1, 3];// Function callconsole.log(score_of_sorted_array(A, B, N, M));// This code is contributed by Tapesh(tapeshdua420) |
Output
6
Time complexity: O(N + M)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
