Suma común mínima de arrays K después de eliminar parte de su sufijo

 Dadas K (K > 2) arrays de diferentes tamaños en una lista 2D arr[][] donde los elementos de cada array no son negativos. Encuentre la suma común mínima de K arrays después de eliminar parte del sufijo (posiblemente ninguno) de cada array.

Ejemplos:

Entrada: K = 3, 
arr = {{5, 2, 4}, 
          {1, 4, 1, 1}, 
          {2, 3}}
Salida : 5
Explicación:1ra array: [5, 5+2, 5+2+4], = { 5 , 7, 11} quitar array de sufijos [2, 4]
2da array: [1, 1+4, 1+4+1, 1 +4+1+1], = {1, 5 , 6, 7} eliminar array de sufijos [1, 1]
3ra array: [2, 2+3 ], = {2, 5 } no eliminar nada
5 es la suma común mínima de arrays dadas después de eliminar parte del sufijo.

Entrada: K = 4
arr = {{5, 3}, 
          {1, 4}, 
          {3, 1}, 
          {9, 3, 1}}
Salida : -1
Explicación: L a suma es tan común, por lo tanto imprimir -1. 

Enfoque: La solución del problema se basa en suma de prefijos y hashing . Use la suma de prefijos en toda la array y el valor de la suma de prefijos en el mapa o tabla hash. Ahora, para la primera array de suma de prefijos, encuentre el valor mínimo que está presente en todas las arrays de suma de prefijos utilizando la tabla hash. Siga los pasos que se mencionan a continuación para resolver el problema:

• Obtenga la suma del prefijo de todas las arrays. Mientras realiza la suma de prefijos, haga un hash del valor de la suma de prefijos en un mapa hash para verificar si esta suma de prefijos está presente en todas las arrays o no.
• Como el cálculo previo se realiza en números enteros no negativos. Después del cálculo previo, las arrays estarán en orden no decreciente.
• Ahora recorra la primera array de suma de prefijos y –
  • Compruebe si la suma del prefijo actual está presente en todas las arrays o no utiliza el mapa hash.
  • Si está presente, detenga la iteración y devuélvalo como la suma común mínima.
  • Si no, continúa con la iteración.
• Después de realizar la iteración completa, si no se encuentra tal suma de prefijo, entonces no se puede formar una suma común siguiendo la condición dada.

A continuación se muestra la implementación del enfoque anterior.

// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Precompute for every array
void 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 sum
int 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 code
int 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 program to implement the approach
import 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 program to implement the approach
 
# Precompute for every array
def 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 sum
def 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 code
if __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# program to implement the approach
using 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

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

5

Complejidad de tiempo: O(K * N) donde N es el tamaño máximo de una array
Espacio auxiliar: O(K * N)