Dado un arreglo de tamaño N, necesitamos encontrar el subarreglo de tamaño más pequeño cuya suma sea divisible por el tamaño de arreglo N.
Ejemplos:
Input : arr[] = [1, 1, 2, 2, 4, 2] Output : [2 4] Size of array, N = 6 Following subarrays have sum as multiple of N [1, 1, 2, 2], [2, 4], [1, 1, 2, 2, 4, 2] The smallest among all is [2 4]
Podemos resolver este problema considerando los siguientes hechos,
Let S[i] denotes sum of first i elements i.e. S[i] = a[1] + a[2] .. + a[i] Now subarray arr(i, i + x) has sum multiple of N then, (arr(i] + arr[i+1] + .... + arr[i + x])) % N = 0 (S[i+x] – S[i] ) % N = 0 S[i] % N = S[i + x] % N
Necesitamos encontrar el valor mínimo de x para el cual se cumple la condición anterior. Esto se puede implementar en una única iteración con complejidad de tiempo O(N) utilizando otro arreglo modIdx de tamaño N. El arreglo modIdx se inicializa con todos los elementos como -1. modIdx[k] debe actualizarse con i en cada iteración, donde k = sum % N.
Ahora, en cada iteración, debemos actualizar modIdx[k] de acuerdo con el valor de sum % N.
Necesitamos verificar dos cosas,
Si en cualquier instante k = 0 y es la primera vez que actualizamos modIdx[0] (es decir , modIdx[0] era -1)
Entonces asignamos x a i + 1, porque (i + 1) será la longitud de subarreglo cuya suma es múltiplo de N
En otro caso, cada vez que obtenemos un valor de mod, si este índice no es -1, eso significa que se actualiza por algún otro valor de suma, cuyo índice se almacena en ese índice, actualizamos x con este valor de diferencia, es decir, por i – modIdx [k] .
Después de cada operación anterior, actualizamos el valor mínimo de longitud y el índice inicial y final correspondiente para el subarreglo. Finalmente, esto da la solución a nuestro problema.
Implementación:
C++
// C++ program to find subarray whose sum
// is multiple of size
#include <bits/stdc++.h>
using namespace std;
// Method prints smallest subarray whose sum is
// multiple of size
void printSubarrayMultipleOfN(int arr[], int N)
{
// A direct index table to see if sum % N
// has appeared before or not.
int modIdx[N];
// initialize all mod index with -1
for (int i = 0; i < N; i++)
modIdx[i] = -1;
// initializing minLen and curLen with larger
// values
int minLen = N + 1;
int curLen = N + 1;
// To store sum of array elements
int sum = 0;
// looping for each value of array
int l, r;
for (int i = 0; i < N; i++)
{
sum += arr[i];
sum %= N;
// If this is the first time we have
// got mod value as 0, then S(0, i) % N
// == 0
if (modIdx[sum] == -1 && sum == 0)
curLen = i + 1;
// If we have reached this mod before then
// length of subarray will be i - previous_position
if (modIdx[sum] != -1)
curLen = i - modIdx[sum];
// choose minimum length as subarray till now
if (curLen < minLen)
{
minLen = curLen;
// update left and right indices of subarray
l = modIdx[sum] + 1;
r = i;
}
modIdx[sum] = i;
}
// print subarray
for (int i = l; i <= r; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver code to test above method
int main()
{
int arr[] = {1, 1, 2, 2, 4, 2};
int N = sizeof(arr) / sizeof(int);
printSubarrayMultipleOfN(arr, N);
return 0;
}
Java
// Java program to find subarray whose sum
// is multiple of size
class GFG {
// Method prints smallest subarray whose sum is
// multiple of size
static void printSubarrayMultipleOfN(int arr[],
int N)
{
// A direct index table to see if sum % N
// has appeared before or not.
int modIdx[] = new int[N];
// initialize all mod index with -1
for (int i = 0; i < N; i++)
modIdx[i] = -1;
// initializing minLen and curLen with
// larger values
int minLen = N + 1;
int curLen = N + 1;
// To store sum of array elements
int sum = 0;
// looping for each value of array
int l = 0, r = 0;
for (int i = 0; i < N; i++) {
sum += arr[i];
sum %= N;
// If this is the first time we
// have got mod value as 0, then
// S(0, i) % N == 0
if (modIdx[sum] == -1 && sum == 0)
curLen = i + 1;
// If we have reached this mod before
// then length of subarray will be i
// - previous_position
if (modIdx[sum] != -1)
curLen = i - modIdx[sum];
// choose minimum length as subarray
// till now
if (curLen < minLen) {
minLen = curLen;
// update left and right indices
// of subarray
l = modIdx[sum] + 1;
r = i;
}
modIdx[sum] = i;
}
// print subarray
for (int i = l; i <= r; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program
public static void main(String arg[])
{
int arr[] = { 1, 1, 2, 2, 4, 2 };
int N = arr.length;
printSubarrayMultipleOfN(arr, N);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find subarray # whose sum is multiple of size # Method prints smallest subarray # whose sum is multiple of size def printSubarrayMultipleOfN(arr, N): # A direct index table to see if sum % N # has appeared before or not. modIdx = [0 for i in range(N)] # initialize all mod index with -1 for i in range(N): modIdx[i] = -1 # initializing minLen and curLen # with larger values minLen = N + 1 curLen = N + 1 # To store sum of array elements sum = 0 # looping for each value of array l = 0; r = 0 for i in range(N): sum += arr[i] sum %= N # If this is the first time we have # got mod value as 0, then S(0, i) % N # == 0 if (modIdx[sum] == -1 and sum == 0): curLen = i + 1 # If we have reached this mod before then # length of subarray will be i - previous_position if (modIdx[sum] != -1): curLen = i - modIdx[sum] # choose minimum length as subarray till now if (curLen < minLen): minLen = curLen # update left and right indices of subarray l = modIdx[sum] + 1 r = i modIdx[sum] = i # print subarray for i in range(l, r + 1): print(arr[i] , " ", end = "") print() # Driver program arr = [1, 1, 2, 2, 4, 2] N = len(arr) printSubarrayMultipleOfN(arr, N) # This code is contributed by Anant Agarwal.
C#
// C# program to find subarray whose sum
// is multiple of size
using System;
class GFG {
// Method prints smallest subarray whose sum is
// multiple of size
static void printSubarrayMultipleOfN(int []arr,
int N)
{
// A direct index table to see if sum % N
// has appeared before or not.
int []modIdx = new int[N];
// initialize all mod index with -1
for (int i = 0; i < N; i++)
modIdx[i] = -1;
// initializing minLen and curLen with
// larger values
int minLen = N + 1;
int curLen = N + 1;
// To store sum of array elements
int sum = 0;
// looping for each value of array
int l = 0, r = 0;
for (int i = 0; i < N; i++) {
sum += arr[i];
sum %= N;
// If this is the first time we
// have got mod value as 0, then
// S(0, i) % N == 0
if (modIdx[sum] == -1 && sum == 0)
curLen = i + 1;
// If we have reached this mod before
// then length of subarray will be i
// - previous_position
if (modIdx[sum] != -1)
curLen = i - modIdx[sum];
// choose minimum length as subarray
// till now
if (curLen < minLen) {
minLen = curLen;
// update left and right indices
// of subarray
l = modIdx[sum] + 1;
r = i;
}
modIdx[sum] = i;
}
// print subarray
for (int i = l; i <= r; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver Code
public static void Main()
{
int []arr = {1, 1, 2, 2, 4, 2};
int N = arr.Length;
printSubarrayMultipleOfN(arr, N);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find subarray
// whose sum is multiple of size
// Method prints smallest subarray
// whose sum is multiple of size
function printSubarrayMultipleOfN($arr,
$N)
{
// A direct index table to see
// if sum % N has appeared
// before or not.
$modIdx = array();
// initialize all mod
// index with -1
for ($i = 0; $i < $N; $i++)
$modIdx[$i] = -1;
// initializing minLen and
// curLen with larger values
$minLen = $N + 1;
$curLen = $N + 1;
// To store sum of
// array elements
$sum = 0;
// looping for each
// value of array
$l; $r;
for ($i = 0; $i < $N; $i++)
{
$sum += $arr[$i];
$sum %= $N;
// If this is the first time
// we have got mod value as 0,
// then S(0, i) % N == 0
if ($modIdx[$sum] == -1 &&
$sum == 0)
$curLen = $i + 1;
// If we have reached this mod
// before then length of subarray
// will be i - previous_position
if ($modIdx[$sum] != -1)
$curLen = $i - $modIdx[$sum];
// choose minimum length
// as subarray till now
if ($curLen < $minLen)
{
$minLen = $curLen;
// update left and right
// indices of subarray
$l = $modIdx[$sum] + 1;
$r = $i;
}
$modIdx[$sum] = $i;
}
// print subarray
for ($i = $l; $i <= $r; $i++)
echo $arr[$i] , " ";
echo "\n" ;
}
// Driver Code
$arr = array(1, 1, 2, 2, 4, 2);
$N = count($arr);
printSubarrayMultipleOfN($arr, $N);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find subarray whose sum
// is multiple of size
// Method prints smallest subarray whose sum is
// multiple of size
function printSubarrayMultipleOfN(arr, N)
{
// A direct index table to see if sum % N
// has appeared before or not.
let modIdx = new Array(N);
// initialize all mod index with -1
for (let i = 0; i < N; i++)
modIdx[i] = -1;
// initializing minLen and curLen with
// larger values
let minLen = N + 1;
let curLen = N + 1;
// To store sum of array elements
let sum = 0;
// looping for each value of array
let l = 0, r = 0;
for (let i = 0; i < N; i++) {
sum += arr[i];
sum %= N;
// If this is the first time we
// have got mod value as 0, then
// S(0, i) % N == 0
if (modIdx[sum] == -1 && sum == 0)
curLen = i + 1;
// If we have reached this mod before
// then length of subarray will be i
// - previous_position
if (modIdx[sum] != -1)
curLen = i - modIdx[sum];
// choose minimum length as subarray
// till now
if (curLen < minLen) {
minLen = curLen;
// update left and right indices
// of subarray
l = modIdx[sum] + 1;
r = i;
}
modIdx[sum] = i;
}
// print subarray
for (let i = l; i <= r; i++)
document.write(arr[i] + " ");
document.write("</br>");
}
let arr = [1, 1, 2, 2, 4, 2];
let N = arr.length;
printSubarrayMultipleOfN(arr, N);
</script>
Producción
2 4
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA