Longitud del subarreglo más pequeño que se eliminará para hacer que la suma de los elementos restantes sea divisible por K

Dada una array arr[] de enteros y un entero K , la tarea es encontrar la longitud del subarreglo más pequeño que debe eliminarse de modo que la suma de los elementos restantes de la array sea divisible por K . No se permite la eliminación de toda la array. Si es imposible, imprima “-1” .

Ejemplos:

Entrada: arr[] = {3, 1, 4, 2}, K = 6
Salida: 1
Explicación: Suma de los elementos del arreglo = 10, que no es divisible por 6. Después de eliminar el subarreglo {4}, la suma de los elementos restantes elementos es 6. Por lo tanto, la longitud del subarreglo eliminado es 1.

Entrada: arr[] = {3, 6, 7, 1}, K = 9
Salida: 2
Explicación: Suma de los elementos del arreglo = 17, que no es divisible por 9. Después de quitar el subarreglo {7, 1} y el, la suma de los elementos restantes es 9. Por lo tanto, la longitud del subarreglo eliminado es 2.

Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles a partir del arreglo dado arr[] excluyendo el subarreglo de longitud N . Ahora, encuentre la longitud mínima del subarreglo tal que la diferencia entre la suma de todos los elementos del arreglo y la suma de los elementos en ese subarreglo sea divisible por K . Si no existe tal subarreglo, imprima «-1» . 

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la siguiente observación:

((total_sum – subarray_sum) % K + subarray_sum % K) debe ser igual a total_sum % K.
Pero, (total_sum – subarray_sum) % K == 0 debe ser verdadero.

Por lo tanto, total_sum % K == subarray_sum % K, por lo que tanto subarray_sum como total_sum deberían dejar el mismo resto cuando se dividen por K. Por lo tanto, la tarea es encontrar la longitud del subarreglo más pequeño cuya suma de elementos dejará un resto de (total_sum %K).

Siga los pasos a continuación para resolver este problema:

• Inicialice la variable res como INT_MAX para almacenar la longitud mínima del subarreglo que se eliminará.
• Calcule total_sum y el resto que deja cuando se divide por K .
• Cree una array auxiliar modArr[] para almacenar el resto de cada arr[i] cuando se divide por K como:

modArr[i] = (arr[i] + K) % K .
donde, 
K se ha agregado al calcular el resto para manejar el caso de números enteros negativos.

• Atraviese la array dada y mantenga un mapa unordered_map para almacenar la posición reciente del resto encontrado y realizar un seguimiento del subarreglo mínimo requerido que tenga el resto igual que target_remainder .
• Si existe alguna clave en el mapa que sea igual a (curr_remainder – target_remainder + K) % K , almacene esa longitud de subarreglo en res variable como el mínimo de res y la longitud actual encontrada.
• Después de lo anterior, si res no cambia, imprime «-1». De lo contrario, imprime el valor de res .

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

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the length of the
// smallest subarray to be removed such
// that sum of elements is divisible by K
void removeSmallestSubarray(int arr[],
                            int n, int k)
{
    // Stores the remainder of each
    // arr[i] when divided by K
    int mod_arr[n];
  
    // Stores total sum of elements
    int total_sum = 0;
  
    // K has been added to each arr[i]
    // to handle -ve integers
    for (int i = 0; i < n; i++) {
        mod_arr[i] = (arr[i] + k) % k;
  
        // Update the total sum
        total_sum += arr[i];
    }
  
    // Remainder when total_sum
    // is divided by K
    int target_remainder
        = total_sum % k;
  
    // If given array is already
    // divisible by K
    if (target_remainder == 0) {
        cout << "0";
        return;
    }
  
    // Stores curr_remainder and the
    // most recent index at which
    // curr_remainder has occurred
    unordered_map<int, int> map1;
    map1[0] = -1;
  
    int curr_remainder = 0;
  
    // Stores required answer
    int res = INT_MAX;
  
    for (int i = 0; i < n; i++) {
  
        // Add current element to
        // curr_sum and take mod
        curr_remainder = (curr_remainder
                          + arr[i] + k)
                         % k;
  
        // Update current remainder index
        map1[curr_remainder] = i;
  
        int mod
            = (curr_remainder
               - target_remainder
               + k)
              % k;
  
        // If mod already exists in map
        // the subarray exists
        if (map1.find(mod) != map1.end())
            res = min(res, i - map1[mod]);
    }
  
    // If not possible
    if (res == INT_MAX || res == n) {
        res = -1;
    }
  
    // Print the result
    cout << res;
}
  
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 3, 1, 4, 2 };
  
    // Size of array
    int N = sizeof(arr) / sizeof(arr[0]);
  
    // Given K
    int K = 6;
  
    // Function Call
    removeSmallestSubarray(arr, N, K);
  
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
  
// Function to find the length of the
// smallest subarray to be removed such
// that sum of elements is divisible by K
static void removeSmallestSubarray(int arr[],
                                   int n, int k)
{
  // Stores the remainder of each
  // arr[i] when divided by K
  int []mod_arr = new int[n];
  
  // Stores total sum of
  // elements
  int total_sum = 0;
  
  // K has been added to each 
  // arr[i] to handle -ve integers
  for (int i = 0; i < n; i++) 
  {
    mod_arr[i] = (arr[i] + 
                  k) % k;
  
    // Update the total sum
    total_sum += arr[i];
  }
  
  // Remainder when total_sum
  // is divided by K
  int target_remainder = 
      total_sum % k;
  
  // If given array is already
  // divisible by K
  if (target_remainder == 0) 
  {
    System.out.print("0");
    return;
  }
  
  // Stores curr_remainder and the
  // most recent index at which
  // curr_remainder has occurred
  HashMap<Integer,
          Integer> map1 = 
          new HashMap<>();
  map1.put(0, -1);
  
  int curr_remainder = 0;
  
  // Stores required answer
  int res = Integer.MAX_VALUE;
  
  for (int i = 0; i < n; i++) 
  {
    // Add current element to
    // curr_sum and take mod
    curr_remainder = (curr_remainder + 
                      arr[i] + k) % k;
  
    // Update current remainder 
    // index
    map1.put(curr_remainder, i);
  
    int mod = (curr_remainder - 
               target_remainder + 
               k) % k;
  
    // If mod already exists in 
    // map the subarray exists
    if (map1.containsKey(mod))
      res = Math.min(res, i - 
                     map1.get(mod));
  }
  
  // If not possible
  if (res == Integer.MAX_VALUE || 
      res == n) 
  {
    res = -1;
  }
  
  // Print the result
  System.out.print(res);
}
  
// Driver Code
public static void main(String[] args)
{
  // Given array arr[]
  int arr[] = {3, 1, 4, 2};
  
  // Size of array
  int N = arr.length;
  
  // Given K
  int K = 6;
  
  // Function Call
  removeSmallestSubarray(arr, N, K);
}
}
  
// This code is contributed by gauravrajput1

# Python3 program for the above approach
import sys
  
# Function to find the length of the
# smallest subarray to be removed such
# that sum of elements is divisible by K
def removeSmallestSubarray(arr, n, k):
      
    # Stores the remainder of each
    # arr[i] when divided by K
    mod_arr = [0] * n
   
    # Stores total sum of elements
    total_sum = 0
   
    # K has been added to each arr[i]
    # to handle -ve integers
    for i in range(n) :
        mod_arr[i] = (arr[i] + k) % k
   
        # Update the total sum
        total_sum += arr[i]
          
    # Remainder when total_sum
    # is divided by K
    target_remainder = total_sum % k
   
    # If given array is already
    # divisible by K
    if (target_remainder == 0):
        print("0")
        return
      
    # Stores curr_remainder and the
    # most recent index at which
    # curr_remainder has occurred
    map1 = {}
    map1[0] = -1
   
    curr_remainder = 0
   
    # Stores required answer
    res = sys.maxsize 
   
    for i in range(n):
          
        # Add current element to
        # curr_sum and take mod
        curr_remainder = (curr_remainder + 
                             arr[i] + k) % k
   
        # Update current remainder index
        map1[curr_remainder] = i
   
        mod = (curr_remainder - 
             target_remainder + k) % k
   
        # If mod already exists in map
        # the subarray exists
        if (mod in map1.keys()):
            res = min(res, i - map1[mod])
      
    # If not possible
    if (res == sys.maxsize or res == n):
        res = -1
      
    # Print the result
    print(res)
  
# Driver Code
  
# Given array arr[]
arr = [ 3, 1, 4, 2 ]
   
# Size of array
N = len(arr) 
   
# Given K
K = 6
   
# Function Call
removeSmallestSubarray(arr, N, K)
  
# This code is contributed by susmitakundugoaldanga

// C# program for the
// above approach
using System;
using System.Collections.Generic;
  
class GFG{
  
// Function to find the length of the
// smallest subarray to be removed such
// that sum of elements is divisible by K
static void removeSmallestSubarray(int []arr,
                                   int n, int k)
{
    
  // Stores the remainder of each
  // arr[i] when divided by K
  int []mod_arr = new int[n];
  
  // Stores total sum of
  // elements
  int total_sum = 0;
  
  // K has been added to each 
  // arr[i] to handle -ve integers
  for(int i = 0; i < n; i++) 
  {
    mod_arr[i] = (arr[i] + k) % k;
  
    // Update the total sum
    total_sum += arr[i];
  }
  
  // Remainder when total_sum
  // is divided by K
  int target_remainder = total_sum % k;
  
  // If given array is already
  // divisible by K
  if (target_remainder == 0) 
  {
    Console.Write("0");
    return;
  }
  
  // Stores curr_remainder and the
  // most recent index at which
  // curr_remainder has occurred
  Dictionary<int,
             int> map1 = new Dictionary<int,
                                        int>();
    
  map1.Add(0, -1);
  
  int curr_remainder = 0;
  
  // Stores required answer
  int res = int.MaxValue;
  
  for(int i = 0; i < n; i++) 
  {
      
    // Add current element to
    // curr_sum and take mod
    curr_remainder = (curr_remainder + 
                      arr[i] + k) % k;
  
    // Update current remainder 
    // index
    map1[curr_remainder] = i;
  
    int mod = (curr_remainder - 
               target_remainder + 
               k) % k;
  
    // If mod already exists in 
    // map the subarray exists
    if (map1.ContainsKey(mod))
      res = Math.Min(res, i - 
                     map1[mod]);
  }
  
  // If not possible
  if (res == int.MaxValue || 
      res == n) 
  {
    res = -1;
  }
    
  // Print the result
  Console.Write(res);
}
  
// Driver Code
public static void Main(String[] args)
{
    
  // Given array []arr
  int []arr = { 3, 1, 4, 2 };
  
  // Size of array
  int N = arr.Length;
  
  // Given K
  int K = 6;
  
  // Function Call
  removeSmallestSubarray(arr, N, K);
}
}
  
// This code is contributed by 29AjayKumar

<script>
  
// JavaScript program for the above approach
  
// Function to find the length of the
// smallest subarray to be removed such
// that sum of elements is divisible by K
function removeSmallestSubarray(arr, n, k) {
    // Stores the remainder of each
    // arr[i] when divided by K
    let mod_arr = new Array(n);
  
    // Stores total sum of elements
    let total_sum = 0;
  
    // K has been added to each arr[i]
    // to handle -ve integers
    for (let i = 0; i < n; i++) {
        mod_arr[i] = (arr[i] + k) % k;
  
        // Update the total sum
        total_sum += arr[i];
    }
  
    // Remainder when total_sum
    // is divided by K
    let target_remainder
        = total_sum % k;
  
    // If given array is already
    // divisible by K
    if (target_remainder == 0) {
        document.write("0");
        return;
    }
  
    // Stores curr_remainder and the
    // most recent index at which
    // curr_remainder has occurred
    let map1 = new Map();
    map1.set(0, -1);
  
    let curr_remainder = 0;
  
    // Stores required answer
    let res = Number.MAX_SAFE_INTEGER;
  
    for (let i = 0; i < n; i++) {
  
        // Add current element to
        // curr_sum and take mod
        curr_remainder = (curr_remainder
            + arr[i] + k)
            % k;
  
        // Update current remainder index
        map1.set(curr_remainder, i);
  
        let mod
            = (curr_remainder
                - target_remainder
                + k)
            % k;
  
        // If mod already exists in map
        // the subarray exists
        if (map1.has(mod))
            res = Math.min(res, i - map1.get(mod));
    }
  
    // If not possible
    if (res == Number.MAX_SAFE_INTEGER || res == n) {
        res = -1;
    }
  
    // Print the result
    document.write(res);
}
  
// Driver Code
  
// Given array arr[]
let arr = [3, 1, 4, 2];
  
// Size of array
let N = arr.length;
  
// Given K
let K = 6;
  
// Function Call
removeSmallestSubarray(arr, N, K);
  
</script>

1

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array