Dado un arreglo de N enteros no negativos, la tarea es encontrar el tamaño máximo de un subarreglo tal que la suma por pares de los elementos de este subarreglo no sea divisible por un entero dado, K. Además, imprima este subarreglo también. Si hay dos o más subarreglos que cumplen la condición anterior, imprima el primero de la izquierda.
Requisito previo: Subconjunto sin suma de pares divisible por K
Ejemplos:
Input : arr[] = [3, 7, 1, 9, 2]
K = 3
Output : 3
[3, 7, 1]
3 + 7 = 10, 3 + 1 = 4, 7 + 1 = 8, all are
not divisible by 3.
It is not possible to get a subarray of size bigger
than 3 with the above-mentioned property.
[7, 1, 9] is also of the same size but [3, 7, 1] comes first.
Input : arr[] = [2, 4, 4, 3]
K = 4
Output : 2
[2, 4]
2 + 4 = 6 is not divisible by 4.
It is not possible to get a subarray of size bigger
than 2 with the above-mentioned property.
[4, 3] is also of the same size but [2, 4] comes first.
Enfoque ingenuo:
el método ingenuo sería considerar todos los subarreglos. Al considerar un subarreglo, tome los elementos por pares y calcule la suma de los dos elementos del par. Si la suma calculada es divisible por K, ignore este subarreglo y continúe con el siguiente subarreglo. De lo contrario, calcule la suma de otros pares de este subarreglo de manera similar. Si la suma de ningún par es un múltiplo de K, compare el tamaño de este subarreglo con el tamaño máximo obtenido hasta el momento y actualícelo si es necesario.
La complejidad temporal de este método sería O( 
).
Enfoque eficiente (usando hash):
Creamos una tabla hash vacía e insertamos arr[0] % k en ella. Ahora recorremos los elementos restantes y mantenemos una ventana tal que ningún par en la ventana sea divisible por k. Para cada elemento atravesado, eliminamos los elementos iniciales mientras exista un elemento en la ventana actual que forme un par divisible con el elemento actual. Para verificar si hay un elemento en la ventana actual, verificamos si sigue.
1) Si hay un elemento x tal que (K – x % K) es igual a arr[i] % K
2) O arr[i] % k es 0 y existe en el hash.
Una vez que nos aseguramos de eliminar todos los elementos que pueden hacer un par con arr[i], agregamos arr[i] a la ventana actual y verificamos si el tamaño de la ventana actual es mayor que la ventana máxima hasta el momento.
C++
// CPP code to find the subarray with
// no pair sum divisible by K
#include<bits/stdc++.h>
using namespace std;
// function to find the subarray with
// no pair sum divisible by k
void subarrayDivisibleByK(int arr[], int n, int k)
{
// hash table to store the remainders
// obtained on dividing by K
map<int,int> mp;
// s : starting index of the
// current subarray, e : ending
// index of the current subarray, maxs :
// starting index of the maximum
// size subarray so far, maxe : ending
// index of the maximum size subarray
// so far
int s = 0, e = 0, maxs = 0, maxe = 0;
// insert the first element in the set
mp[arr[0] % k]++;
for (int i = 1; i < n; i++)
{
int mod = arr[i] % k;
// Removing starting elements of current
// subarray while there is an element in
// set which makes a pair with mod[i] such
// that the pair sum is divisible.
while (mp[k - mod] != 0 ||
(mod == 0 && mp[mod] != 0))
{
mp[arr[s] % k]--;
s++;
}
// include the current element in
// the current subarray the ending
// index of the current subarray
// increments by one
mp[mod]++;
e++;
// compare the size of the current
// subarray with the maximum size so
// far
if ((e - s) > (maxe - maxs))
{
maxe = e;
maxs = s;
}
}
cout << "The maximum size is "
<< maxe - maxs + 1 << " and "
"the subarray is as follows\n";
for (int i=maxs; i<=maxe; i++)
cout << arr[i] << " ";
}
int main()
{
int k = 3;
int arr[] = {5, 10, 15, 20, 25};
int n = sizeof(arr)/sizeof(arr[0]);
subarrayDivisibleByK(arr, n, k);
return 0;
}
Java
// Java Program to find the subarray with
// no pair sum divisible by K
import java.io.*;
import java.util.*;
public class GFG {
// function to find the subarray with
// no pair sum divisible by k
static void subarrayDivisibleByK(int []arr,
int n, int k)
{
// hash table to store the remainders
// obtained on dividing by K
int []mp = new int[1000];
// s : starting index of the
// current subarray, e : ending
// index of the current subarray, maxs :
// starting index of the maximum
// size subarray so far, maxe : ending
// index of the maximum size subarray
// so far
int s = 0, e = 0, maxs = 0, maxe = 0;
// insert the first element in the set
mp[arr[0] % k]++;
for (int i = 1; i < n; i++)
{
int mod = arr[i] % k;
// Removing starting elements of current
// subarray while there is an element in
// set which makes a pair with mod[i] such
// that the pair sum is divisible.
while (mp[k - mod] != 0 ||
(mod == 0 && mp[mod] != 0))
{
mp[arr[s] % k]--;
s++;
}
// include the current element in
// the current subarray the ending
// index of the current subarray
// increments by one
mp[mod]++;
e++;
// compare the size of the current
// subarray with the maximum size so
// far
if ((e - s) > (maxe - maxs))
{
maxe = e;
maxs = s;
}
}
System.out.print("The maximum size is "
+ (maxe - maxs + 1)
+ " and the subarray is as follows\n");
for (int i = maxs; i <= maxe; i++)
System.out.print(arr[i] + " ");
}
// Driver Code
public static void main(String args[])
{
int k = 3;
int []arr = {5, 10, 15, 20, 25};
int n = arr.length;
subarrayDivisibleByK(arr, n, k);
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
Python3
# Python3 Program to find the subarray with
# no pair sum divisible by K
# function to find the subarray with
# no pair sum divisible by k
def subarrayDivisibleByK(arr, n, k) :
# hash table to store the remainders
# obtained on dividing by K
mp = [0] * 1000
# s : starting index of the
# current subarray, e : ending
# index of the current subarray, maxs :
# starting index of the maximum
# size subarray so far, maxe : ending
# index of the maximum size subarray
# so far
s = 0; e = 0; maxs = 0; maxe = 0;
# insert the first element in the set
mp[arr[0] % k] = mp[arr[0] % k] + 1;
for i in range(1, n):
mod = arr[i] % k
# Removing starting elements of current
# subarray while there is an element in
# set which makes a pair with mod[i] such
# that the pair sum is divisible.
while (mp[k - mod] != 0 or (mod == 0
and mp[mod] != 0)) :
mp[arr[s] % k] = mp[arr[s] % k] - 1
s = s + 1
# include the current element in
# the current subarray the ending
# index of the current subarray
# increments by one
mp[mod] = mp[mod] + 1
e = e + 1
# compare the size of the current
# subarray with the maximum size so
# far
if ((e - s) > (maxe - maxs)) :
maxe = e
maxs = s
print ("The maximum size is {} and the "
" subarray is as follows"
.format((maxe - maxs + 1)))
for i in range(maxs, maxe + 1) :
print ("{} ".format(arr[i]), end="")
# Driver Code
k = 3
arr = [5, 10, 15, 20, 25]
n = len(arr)
subarrayDivisibleByK(arr, n, k)
# This code is contributed by
# Manish Shaw (manishshaw1)
C#
// C# Program to find the subarray with
// no pair sum divisible by K
using System;
using System.Collections;
class GFG {
// function to find the subarray with
// no pair sum divisible by k
static void subarrayDivisibleByK(int []arr,
int n, int k)
{
// hash table to store the remainders
// obtained on dividing by K
int []mp = new int[1000];
// s : starting index of the
// current subarray, e : ending
// index of the current subarray, maxs :
// starting index of the maximum
// size subarray so far, maxe : ending
// index of the maximum size subarray
// so far
int s = 0, e = 0, maxs = 0, maxe = 0;
// insert the first element in the set
mp[arr[0] % k]++;
for (int i = 1; i < n; i++)
{
int mod = arr[i] % k;
// Removing starting elements of current
// subarray while there is an element in
// set which makes a pair with mod[i] such
// that the pair sum is divisible.
while (mp[k - mod] != 0 ||
(mod == 0 && mp[mod] != 0))
{
mp[arr[s] % k]--;
s++;
}
// include the current element in
// the current subarray the ending
// index of the current subarray
// increments by one
mp[mod]++;
e++;
// compare the size of the current
// subarray with the maximum size so
// far
if ((e - s) > (maxe - maxs))
{
maxe = e;
maxs = s;
}
}
Console.Write("The maximum size is " +
(maxe - maxs + 1) +
" and the subarray is as follows\n");
for (int i = maxs; i <= maxe; i++)
Console.Write(arr[i] + " ");
}
// Driver Code
public static void Main()
{
int k = 3;
int []arr = {5, 10, 15, 20, 25};
int n = arr.Length;
subarrayDivisibleByK(arr, n, k);
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
PHP
<?php
// PHP Program to find the
// subarray with no pair
// sum divisible by K
// function to find the subarray
// with no pair sum divisible by k
function subarrayDivisibleByK($arr, $n, $k)
{
// hash table to store the remainders
// obtained on dividing by K
$mp = array_fill(0, 1000, 0);
// s : starting index of the
// current subarray, e : ending
// index of the current subarray, maxs :
// starting index of the maximum
// size subarray so far, maxe : ending
// index of the maximum size subarray
// so far
$s = 0;
$e = 0;
$maxs = 0;
$maxe = 0;
// insert the first
// element in the set
$mp[$arr[0] % $k]++;
for ($i = 1; $i < $n; $i++)
{
$mod = $arr[$i] % $k;
// Removing starting elements
// of current subarray while
// there is an element in set
// which makes a pair with
// mod[i] such that the pair
// sum is divisible.
while ($mp[$k - $mod] != 0 ||
($mod == 0 &&
$mp[$mod] != 0))
{
$mp[$arr[$s] % $k]--;
$s++;
}
// include the current element in
// the current subarray the ending
// index of the current subarray
// increments by one
$mp[$mod]++;
$e++;
// compare the size of the current
// subarray with the maximum size so
// far
if (($e - $s) > ($maxe - $maxs))
{
$maxe = $e;
$maxs = $s;
}
}
echo ("The maximum size is ".
($maxe - $maxs + 1).
" and the subarray is".
" as follows\n");
for ($i = $maxs; $i <= $maxe; $i++)
echo ($arr[$i]." ");
}
// Driver Code
$k = 3;
$arr = array(5, 10, 15, 20, 25);
$n = count($arr);
subarrayDivisibleByK($arr, $n, $k);
// This code is contributed by
// Manish Shaw (manishshaw1)
?>
Javascript
<script>
// JavaScript Program to find the subarray with
// no pair sum divisible by K
// function to find the subarray with
// no pair sum divisible by k
function subarrayDivisibleByK(arr, n, k) {
// hash table to store the remainders
// obtained on dividing by K
var mp = new Array(1000).fill(0);
// s : starting index of the
// current subarray, e : ending
// index of the current subarray, maxs :
// starting index of the maximum
// size subarray so far, maxe : ending
// index of the maximum size subarray
// so far
var s = 0,
e = 0,
maxs = 0,
maxe = 0;
// insert the first element in the set
mp[arr[0] % k]++;
for (var i = 1; i < n; i++) {
var mod = arr[i] % k;
// Removing starting elements of current
// subarray while there is an element in
// set which makes a pair with mod[i] such
// that the pair sum is divisible.
while (mp[k - mod] != 0 || (mod == 0 && mp[mod] != 0)) {
mp[arr[s] % k]--;
s++;
}
// include the current element in
// the current subarray the ending
// index of the current subarray
// increments by one
mp[mod]++;
e++;
// compare the size of the current
// subarray with the maximum size so
// far
if (e - s > maxe - maxs) {
maxe = e;
maxs = s;
}
}
document.write(
"The maximum size is " +
(maxe - maxs + 1) +
" and the subarray is as follows<br>"
);
for (var i = maxs; i <= maxe; i++) document.write(arr[i] + " ");
}
// Driver Code
var k = 3;
var arr = [5, 10, 15, 20, 25];
var n = arr.length;
subarrayDivisibleByK(arr, n, k);
// This code is contributed by rdtank.
</script>
Producción :
The maximum size is 2 and the subarray is as follows 10 15
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por aganjali10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA