Given K (K > 2) arrays of different sizes in a 2D list arr[][] where elements in each array are non-negative. Find the minimum common sum of K arrays after removing part of the suffix(possibly none) from each array.
Examples:
Input: K = 3,
arr = {{5, 2, 4},
{1, 4, 1, 1},
{2, 3}}
Output: 5
Explanation: 1st array: [5, 5+2, 5+2+4], = {5, 7, 11} remove suffix array [2, 4]
2nd array: [1, 1+4, 1+4+1, 1+4+1+1], = {1, 5, 6, 7} remove suffix array [1, 1]
3rd array: [2, 2+3 ], = {2, 5} don’t remove any thing
5 is the minimum common sum of given arrays after removing part of the suffix.Input: K = 4
arr = {{5, 3},
{1, 4},
{3, 1},
{9, 3, 1}}
Output: -1
Explanation: There is so common sum at all, therefore print -1.
Approach: The solution of the problem is based on prefix sum and hashing. Use prefix sum on all the array and hash the prefix sum value in map or hash table. Now for the first prefix sum array find the minimum value which is present in all the prefix sum arrays using the hash table. Follow the steps mentioned below to solve the problem:
- Get the prefix sum of all the arrays. While doing the prefix sum hash the value of prefix sum in a hashmap to check if this prefix sum is present in all the arrays or not.
- As precomputation is done on non-negative integers. After precomputation, arrays will be in non-decreasing order.
- Now traverse through the first prefix sum array and –
- Check if the current prefix sum is present in all the arrays or not using the hash map.
- If present stop iteration and return that as the minimum common sum.
- If not then continue the iteration.
- After the full iteration is done, if there is no such prefix sum found then no common sum can be formed following the given condition.
Below is the implementation of the above approach.
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Precompute for every arrayvoid pre_compute(vector<vector<int> >& arr, int K, unordered_map<int, int>& mp){ for (int i = 0; i < K; i++) { // Size of ith row stored in n int n = arr[i].size(); mp[arr[i][0]] = min(mp[arr[i][0]] + 1, i + 1); // Precomputing ith row for (int j = 1; j < n; j++) { arr[i][j] += arr[i][j - 1]; mp[arr[i][j]] = min(mp[arr[i][j]] + 1, i + 1); } }}// Function to calculate minimum common sumint min_common_sum(vector<vector<int> >& arr, int K){ unordered_map<int, int> mp; // Function call to precompute // every row in arr pre_compute(arr, K, mp); for (int i = 0; i < arr[0].size(); i++) { if (mp[arr[0][i]] == K) return arr[0][i]; } return -1;}// Driver codeint main(){ int K = 3; // All k arrays are stored using 2D vector vector<vector<int> > arr = { { 5, 2, 4 }, { 1, 4, 1, 1 }, { 2, 3 } }; int ans = min_common_sum(arr, K); cout << ans; return 0;} |
Java
// Java program to implement the approachimport java.util.*;class GFG{ // Precompute for every array static HashMap<Integer,Integer> pre_compute(int[][] arr, int K, HashMap<Integer,Integer> mp) { for (int i = 0; i < K; i++) { // Size of ith row stored in n int n = arr[i].length; if(mp.containsKey(arr[i][0])) mp.put(arr[i][0], Math.min(mp.get(arr[i][0]) + 1, i + 1)); else mp.put(arr[i][0], Math.min(1, i + 1)); // Precomputing ith row for (int j = 1; j < n; j++) { arr[i][j] += arr[i][j - 1]; if(mp.containsKey(arr[i][j])) mp.put(arr[i][j], Math.min(mp.get(arr[i][j]) + 1, i + 1)); else mp.put(arr[i][j], Math.min(1, i + 1)); } } return mp; } // Function to calculate minimum common sum static int min_common_sum(int[][] arr, int K) { HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Function call to precompute // every row in arr mp = pre_compute(arr, K, mp); for (int i = 0; i < arr[0].length; i++) { if (mp.get(arr[0][i]) == K) return arr[0][i]; } return -1; } // Driver code public static void main(String[] args) { int K = 3; // All k arrays are stored using 2D vector int[][] arr = { { 5, 2, 4 ,0}, { 1, 4, 1, 1 }, { 2, 3,0,0 } }; int ans = min_common_sum(arr, K); System.out.print(ans); }}// This code is contributed by shikhasingrajput |
Python3
# python3 program to implement the approach# Precompute for every arraydef pre_compute(arr, K, mp): for i in range(0, K): # Size of ith row stored in n n = len(arr[i]) mp[arr[i][0]] = min( (mp[arr[i][0]] if arr[i][0] in mp else 0) + 1, i + 1) # Precomputing ith row for j in range(1, n): arr[i][j] += arr[i][j - 1] mp[arr[i][j]] = min((mp[arr[i][j]] if arr[i][j] in mp else 0) + 1, i + 1)# Function to calculate minimum common sumdef min_common_sum(arr, K): mp = {} # Function call to precompute # every row in arr pre_compute(arr, K, mp) for i in range(0, len(arr[0])): if (mp[arr[0][i]] == K): return arr[0][i] return -1# Driver codeif __name__ == "__main__": K = 3 # All k arrays are stored using 2D vector arr = [[5, 2, 4], [1, 4, 1, 1], [2, 3]] ans = min_common_sum(arr, K) print(ans) # This code is contributed by rakeshsahni |
C#
// C# program to implement the approachusing System;using System.Collections.Generic;public class GFG{ // Precompute for every array static Dictionary<int,int> pre_compute(int[,] arr, int K, Dictionary<int,int> mp) { for (int i = 0; i < K; i++) { // Size of ith row stored in n int n = arr.GetLength(1); if(mp.ContainsKey(arr[i,0])) mp[arr[i,0]]= Math.Min(mp[arr[i,0]] + 1, i + 1); else mp.Add(arr[i,0], Math.Min(1, i + 1)); // Precomputing ith row for (int j = 1; j < n; j++) { arr[i,j] += arr[i,j - 1]; if(mp.ContainsKey(arr[i,j])) mp[arr[i,j]] = Math.Min(mp[arr[i,j]] + 1, i + 1); else mp.Add(arr[i,j], Math.Min(1, i + 1)); } } return mp; } // Function to calculate minimum common sum static int min_common_sum(int[,] arr, int K) { Dictionary<int,int> mp = new Dictionary<int,int>(); // Function call to precompute // every row in arr mp = pre_compute(arr, K, mp); for (int i = 0; i < arr.GetLength(0); i++) { if (mp[arr[0,i]] == K) return arr[0,i]; } return -1; } // Driver code public static void Main(String[] args) { int K = 3; // All k arrays are stored using 2D vector int[,] arr = { { 5, 2, 4 ,0}, { 1, 4, 1, 1 }, { 2, 3,0,0 } }; int ans = min_common_sum(arr, K); Console.Write(ans); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Precompute for every array function pre_compute(arr, K, mp) { for (let i = 0; i < K; i++) { // Size of ith row stored in n let n = arr[i].length; mp.set(arr[i][0], 0); if (!mp.has(arr[i])) mp.set(arr[i][0], Math.min(mp.get(arr[i][0]) + 1, i + 1)); // Precomputing ith row for (let j = 1; j < n; j++) { arr[i][j] += arr[i][j - 1]; if (mp.has(arr[i][j])) mp.set(arr[i][j], Math.min(mp.get(arr[i][j]) + 1, i + 1)); else mp.set(arr[i][j], 0) } } return mp; } // Function to calculate minimum common sum function min_common_sum(arr, K) { let mp = new Map(); // Function call to precompute // every row in arr mp = pre_compute(arr, K, mp); for (let i = 0; i < arr[0].length; i++) { if (mp.get(arr[0][i]) == K) return arr[0][i]; } return -1; } // Driver code let K = 3; // All k arrays are stored using 2D vector let arr = [[5, 2, 4], [1, 4, 1, 1], [2, 3]]; let ans = min_common_sum(arr, K); document.write(ans); // This code is contributed by Potta Lokesh </script> |
Output
5
Time Complexity: O(K * N) where N is the maximum size of an array
Auxiliary Space: O(K * 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!
Share your thoughts in the comments
