Given an array arr[] of length n and an integer k, the task is to find the number of indices from 2 to n-1 in an array having a difference of the sum of the left and right sub arrays equal to the multiple of the given number k.
Examples:
Input: arr[] = {1, 2, 3, 3, 1, 1}, k = 4
Output: 2
Explanation: The only possible indices are 4 and 5Input: arr[] = {1, 2, 3, 4, 5}, k = 1
Output: 3
Approach:
- Create a prefix array that contains the sum of the elements on the left and the suffix array which contains the sum of elements on the right.
- Check for every index the difference of the sum on the left and right and increase the counter if it is divisible by k.
Below is the implementation of the above approach:
CPP
// C++ code to count of elements such that // difference between the sum of left and right // sub-arrays are equal to a multiple of k#include <bits/stdc++.h>using namespace std;// Functions to find the no of elementsint noOfElement(int a[], int n, int k){ // Creating a prefix array int prefix[n]; // Starting element of prefix array // will be the first element // of given array prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Creating a suffix array; int suffix[n]; // Last element of suffix array will // be the last element of given array suffix[n - 1] = a[n - 1]; for (int i = n - 2; i >= 0; i--) { suffix[i] = suffix[i + 1] + a[i]; } // Checking difference of left and right half // is divisible by k or not. int cnt = 0; for (int i = 1; i < n - 1; i++) { if ((prefix[i] - suffix[i]) % k == 0 || (suffix[i] - prefix[i]) % k == 0) { cnt = cnt + 1; } } return cnt;}// Driver codeint main(){ int a[] = { 1, 2, 3, 3, 1, 1 }; int k = 4; int n = sizeof(a) / sizeof(a[0]); cout << noOfElement(a, n, k); return 0;} |
Java
// Java code to count of elements such that // difference between the sum of left and right // sub-arrays are equal to a multiple of kclass GFG{// Functions to find the no of elementsstatic int noOfElement(int a[], int n, int k){ // Creating a prefix array int []prefix = new int[n]; // Starting element of prefix array // will be the first element // of given array prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Creating a suffix array; int []suffix = new int[n]; // Last element of suffix array will // be the last element of given array suffix[n - 1] = a[n - 1]; for (int i = n - 2; i >= 0; i--) { suffix[i] = suffix[i + 1] + a[i]; } // Checking difference of left and right half // is divisible by k or not. int cnt = 0; for (int i = 1; i < n - 1; i++) { if ((prefix[i] - suffix[i]) % k == 0 || (suffix[i] - prefix[i]) % k == 0) { cnt = cnt + 1; } } return cnt;}// Driver codepublic static void main(String[] args){ int a[] = { 1, 2, 3, 3, 1, 1 }; int k = 4; int n = a.length; System.out.print(noOfElement(a, n, k));}}// This code is contributed by Rajput-Ji |
Python
# Python3 code to count of elements such that# difference between the sum of left and right# sub-arrays are equal to a multiple of k# Functions to find the no of elementsdef noOfElement(a, n, k): # Creating a prefix array prefix = [0] * n # Starting element of prefix array # will be the first element # of given array prefix[0] = a[0] for i in range(1, n): prefix[i] = prefix[i - 1] + a[i] # Creating a suffix array suffix = [0] * n # Last element of suffix array will # be the last element of given array suffix[n - 1] = a[n - 1] for i in range(n - 2, -1, -1): suffix[i] = suffix[i + 1] + a[i] # Checking difference of left and right half # is divisible by k or not. cnt = 0 for i in range(1, n - 1): if ((prefix[i] - suffix[i]) % k == 0 or (suffix[i] - prefix[i]) % k == 0): cnt = cnt + 1 return cnt# Driver codea = [ 1, 2, 3, 3, 1, 1 ]k = 4n = len(a)print(noOfElement(a, n, k))# This code is contributed by mohit kumar 29 |
C#
// C# code to count of elements such that // difference between the sum of left and right // sub-arrays are equal to a multiple of kusing System;class GFG{ // Functions to find the no of elements static int noOfElement(int []a, int n, int k) { // Creating a prefix array int []prefix = new int[n]; // Starting element of prefix array // will be the first element // of given array prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Creating a suffix array; int []suffix = new int[n]; // Last element of suffix array will // be the last element of given array suffix[n - 1] = a[n - 1]; for (int i = n - 2; i >= 0; i--) { suffix[i] = suffix[i + 1] + a[i]; } // Checking difference of left and right half // is divisible by k or not. int cnt = 0; for (int i = 1; i < n - 1; i++) { if ((prefix[i] - suffix[i]) % k == 0 || (suffix[i] - prefix[i]) % k == 0) { cnt = cnt + 1; } } return cnt; } // Driver code public static void Main() { int []a = { 1, 2, 3, 3, 1, 1 }; int k = 4; int n = a.Length; Console.Write(noOfElement(a, n, k)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript code to count of elements such that // difference between the sum of left and right // sub-arrays are equal to a multiple of k // Functions to find the no of elementsfunction noOfElement(a,n,k){ // Creating a prefix array let prefix = new Array(n); // Starting element of prefix array // will be the first element // of given array prefix[0] = a[0]; for (let i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; } // Creating a suffix array; let suffix = new Array(n); // Last element of suffix array will // be the last element of given array suffix[n - 1] = a[n - 1]; for (let i = n - 2; i >= 0; i--) { suffix[i] = suffix[i + 1] + a[i]; } // Checking difference of left and right half // is divisible by k or not. let cnt = 0; for (let i = 1; i < n - 1; i++) { if ((prefix[i] - suffix[i]) % k == 0 || (suffix[i] - prefix[i]) % k == 0) { cnt = cnt + 1; } } return cnt;} // Driver code let a=[1, 2, 3, 3, 1, 1]; let k = 4; let n = a.length; document.write(noOfElement(a, n, k)); // This code is contributed by patel2127</script> |
Output:
2
Time Complexity: O(n), where n is the size of the array
Auxiliary Space: O(n), as extra space of size n is used to create prefix and suffix array
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!
