Dada una array arr[] de longitud N . La tarea es verificar si existe algún subarreglo cuya suma sea múltiplo de N . Si existe tal subarreglo, imprima el índice inicial y final de ese subarreglo; de lo contrario, imprima -1 . Si hay varios de estos subarreglos, imprima cualquiera de ellos.
Ejemplos:
Entrada: arr[] = {7, 5, 3, 7}
Salida: 0 1
Sub-arreglo del índice 0 a 1 es [7, 5]
la suma de este subarreglo es 12 que es un múltiplo de 4Entrada: arr[] = {3, 7, 14}
Salida: 0 0
Enfoque ingenuo: el enfoque ingenuo consiste en generar todos los subconjuntos y calcular su suma. Si la suma de cualquier subarreglo es un múltiplo de N, devuelva el índice inicial y final.
Complejidad temporal: O(N 3 )
Mejor enfoque: un mejor enfoque es mantener una array de suma de prefijos que almacene la suma de todos los elementos anteriores. Para calcular la suma de un subarreglo entre el índice i y el j, podemos usar la fórmula:
subarreglo suma[i:j] = presum[j]-presum[i-1]
Ahora verifique para cada subarreglo si su suma es un múltiplo de N o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find a subarray
// whose sum is a multiple of N
void CheckSubarray(int arr[], int N)
{
// Prefix sum array to store cumulative sum
int presum[N + 1] = { 0 };
// Single state dynamic programming
// relation for prefix sum array
for (int i = 1; i <= N; i += 1) {
presum[i] = presum[i - 1] + arr[i - 1];
}
// Generating all sub-arrays
for (int i = 1; i <= N; i += 1) {
for (int j = i; j <= N; j += 1) {
// If the sum of the sub-array[i:j]
// is a multiple of N
if ((presum[j] - presum[i - 1]) % N == 0) {
cout << i - 1 << " " << j - 1;
return;
}
}
}
// If the function reaches here it means
// there are no subarrays with sum
// as a multiple of N
cout << -1;
}
// Driver code
int main()
{
int arr[] = { 7, 5, 3, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
CheckSubarray(arr, N);
return 0;
}
Java
// Java implementation of above approach
import java.io.*;
class GFG
{
// Function to find a subarray
// whose sum is a multiple of N
static void CheckSubarray(int arr[], int N)
{
// Prefix sum array to store cumulative sum
int presum[] = new int[N + 1];
// Single state dynamic programming
// relation for prefix sum array
for (int i = 1; i <= N; i += 1)
{
presum[i] = presum[i - 1] + arr[i - 1];
}
// Generating all sub-arrays
for (int i = 1; i <= N; i += 1)
{
for (int j = i; j <= N; j += 1)
{
// If the sum of the sub-array[i:j]
// is a multiple of N
if ((presum[j] - presum[i - 1]) % N == 0)
{
System.out.print((i - 1) + " " + (j - 1));
return;
}
}
}
// If the function reaches here it means
// there are no subarrays with sum
// as a multiple of N
System.out.print(-1);
}
// Driver code
public static void main (String[] args)
{
int []arr = { 7, 5, 3, 7 };
int N = arr.length;
CheckSubarray(arr, N);
}
}
// This code is contributed by anuj_67..
Python3
# Python3 implementation of above approach
# Function to find a subarray
# whose sum is a multiple of N
def CheckSubarray(arr, N):
# Prefix sum array to store cumulative sum
presum=[0 for i in range(N + 1)]
# Single state dynamic programming
# relation for prefix sum array
for i in range(1, N+1):
presum[i] = presum[i - 1] + arr[i - 1]
# Generating all sub-arrays
for i in range(1, N+1):
for j in range(i, N+1):
# If the sum of the sub-array[i:j]
# is a multiple of N
if ((presum[j] - presum[i - 1]) % N == 0):
print(i - 1,j - 1)
return
# If the function reaches here it means
# there are no subarrays with sum
# as a multiple of N
print("-1")
# Driver code
arr = [ 7, 5, 3, 7]
N = len(arr)
CheckSubarray(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to find a subarray
// whose sum is a multiple of N
static void CheckSubarray(int []arr, int N)
{
// Prefix sum array to store cumulative sum
int []presum = new int[N + 1];
// Single state dynamic programming
// relation for prefix sum array
for (int i = 1; i <= N; i += 1)
{
presum[i] = presum[i - 1] + arr[i - 1];
}
// Generating all sub-arrays
for (int i = 1; i <= N; i += 1)
{
for (int j = i; j <= N; j += 1)
{
// If the sum of the sub-array[i:j]
// is a multiple of N
if ((presum[j] - presum[i - 1]) % N == 0)
{
Console.Write((i - 1) + " " + (j - 1));
return;
}
}
}
// If the function reaches here it means
// there are no subarrays with sum
// as a multiple of N
Console.Write(-1);
}
// Driver code
public static void Main ()
{
int []arr = { 7, 5, 3, 7 };
int N = arr.Length;
CheckSubarray(arr, N);
}
}
// This code is contributed by anuj_67..
Javascript
<script>
// Javascript implementation of above approach
// Function to find a subarray
// whose sum is a multiple of N
function CheckSubarray(arr, N)
{
// Prefix sum array to store cumulative sum
let presum = new Array(N + 1).fill(0);
// Single state dynamic programming
// relation for prefix sum array
for (let i = 1; i <= N; i += 1) {
presum[i] = presum[i - 1] + arr[i - 1];
}
// Generating all sub-arrays
for (let i = 1; i <= N; i += 1) {
for (let j = i; j <= N; j += 1) {
// If the sum of the sub-array[i:j]
// is a multiple of N
if ((presum[j] - presum[i - 1]) % N == 0) {
document.write((i - 1) + " " + (j - 1));
return;
}
}
}
// If the function reaches here it means
// there are no subarrays with sum
// as a multiple of N
document.write(-1);
}
// Driver code
let arr = [ 7, 5, 3, 7 ];
let N = arr.length;
CheckSubarray(arr, N);
</script>
Producción:
0 1
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque Eficiente: La idea es utilizar el Principio de Pigeon-Hole. Supongamos que los elementos de la array son a 1 , a 2 … a N .
Para una secuencia de números como sigue:
un 1 , un 1 + un 2 , un 1 + un 2 + un 3 , …, un 1 + un 2 + un 3 + … + un norte
En la secuencia anterior, hay N términos. Hay dos casos posibles:
- Si una de las sumas de prefijos anteriores es un múltiplo de N , imprima los i -ésimos índices del subarreglo.
- Si Ninguno de los elementos de secuencia anteriores se encuentra en la clase de módulo 0 de N , quedan (N – 1) clases de módulo. Por el principio del casillero , hay N palomas (elementos de la secuencia de suma de prefijos) y (N – 1) agujeros (clases de módulo), podemos decir que al menos dos elementos estarían en la misma clase de módulo. La diferencia entre estos dos elementos daría un subarreglo cuya suma será un múltiplo de N .
Se pudo ver que siempre es posible obtener tal subarreglo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check is there exists a
// subarray whose sum is a multiple of N
void CheckSubarray(int arr[], int N)
{
// Prefix sum array to store cumulative sum
int presum[N + 1] = { 0 };
// Single state dynamic programming
// relation for prefix sum array
for (int i = 1; i <= N; i += 1) {
presum[i] = presum[i - 1] + arr[i - 1];
}
// Modulo class vector
vector<int> moduloclass[N];
// Storing the index value in the modulo class vector
for (int i = 1; i <= N; i += 1) {
moduloclass[presum[i] % N].push_back(i - 1);
}
// If there exists a sub-array with
// starting index equal to zero
if (moduloclass[0].size() > 0) {
cout << 0 << " " << moduloclass[0][0];
return;
}
for (int i = 1; i < N; i += 1) {
// In this class, there are more than two presums%N
// Hence difference of any two subarrays would be a
// multiple of N
if (moduloclass[i].size() >= 2) {
// 0 based indexing
cout << moduloclass[i][0] + 1 << " " << moduloclass[i][1];
return;
}
}
}
// Driver code
int main()
{
int arr[] = { 7, 3, 5, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
CheckSubarray(arr, N);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
class GFG
{
// Function to check is there exists a
// subarray whose sum is a multiple of N
static void CheckSubarray(int arr[], int N)
{
// Prefix sum array to store cumulative sum
int[] presum = new int[N + 1];
// Single state dynamic programming
// relation for prefix sum array
for (int i = 1; i <= N; i += 1)
{
presum[i] = presum[i - 1] + arr[i - 1];
}
// Modulo class vector
Vector<Integer>[] moduloclass = new Vector[N];
for (int i = 0; i < N; i += 1)
{
moduloclass[i] = new Vector<>();
}
// Storing the index value
// in the modulo class vector
for (int i = 1; i <= N; i += 1)
{
moduloclass[presum[i] % N].add(i - 1);
}
// If there exists a sub-array with
// starting index equal to zero
if (moduloclass[0].size() > 0)
{
System.out.print(0 + " " +
moduloclass[0].get(0));
return;
}
for (int i = 1; i < N; i += 1)
{
// In this class, there are more than
// two presums%N. Hence difference of
// any two subarrays would be a multiple of N
if (moduloclass[i].size() >= 2)
{
// 0 based indexing
System.out.print(moduloclass[i].get(0) + 1 +
" " + moduloclass[i].get(1));
return;
}
}
}
// Driver code
public static void main(String args[])
{
int arr[] = {7, 3, 5, 2};
int N = arr.length;
CheckSubarray(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 implementation of above approach # Function to check is there exists a # subarray whose sum is a multiple of N def CheckSubarray(arr, N): # Prefix sum array to store cumulative sum presum = [0 for i in range(N+1)] # Single state dynamic programming # relation for prefix sum array for i in range(1,N+1): presum[i] = presum[i - 1] + arr[i - 1] # Modulo class vector moduloclass = [[]]*N # Storing the index value in the modulo class vector for i in range(1,N+1,1): moduloclass[presum[i] % N].append(i - 1) # If there exists a sub-array with # starting index equal to zero if (len(moduloclass[0]) > 0): print(0+1,moduloclass[0][0]+2) return for i in range(1,N): # In this class, there are more than two presums%N # Hence difference of any two subarrays would be a # multiple of N if (len(moduloclass[i]) >= 2): # 0 based indexing print(moduloclass[i][0] + 1,moduloclass[i][1]) return # Driver code if __name__ == '__main__': arr = [7, 3, 5, 2] N = len(arr) CheckSubarray(arr, N) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to check is there exists a
// subarray whose sum is a multiple of N
static void CheckSubarray(int []arr, int N)
{
// Prefix sum array to store cumulative sum
int[] presum = new int[N + 1];
// Single state dynamic programming
// relation for prefix sum array
for (int i = 1; i <= N; i += 1)
{
presum[i] = presum[i - 1] + arr[i - 1];
}
// Modulo class vector
List<int>[] moduloclass = new List<int>[N];
for (int i = 0; i < N; i += 1)
{
moduloclass[i] = new List<int>();
}
// Storing the index value
// in the modulo class vector
for (int i = 1; i <= N; i += 1)
{
moduloclass[presum[i] % N].Add(i - 1);
}
// If there exists a sub-array with
// starting index equal to zero
if (moduloclass[0].Count > 0)
{
Console.Write(0 + " " +
moduloclass[0][0]);
return;
}
for (int i = 1; i < N; i += 1)
{
// In this class, there are more than
// two presums%N. Hence difference of
// any two subarrays would be a multiple of N
if (moduloclass[i].Count >= 2)
{
// 0 based indexing
Console.Write(moduloclass[i][0] + 1 +
" " + moduloclass[i][1]);
return;
}
}
}
// Driver code
public static void Main(String []args)
{
int []arr = {7, 3, 5, 2};
int N = arr.Length;
CheckSubarray(arr, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of above approach
// Function to check is there exists a
// subarray whose sum is a multiple of N
function CheckSubarray(arr, N)
{
// Prefix sum array to store cumulative sum
let presum = new Array(N + 1);
for(let i = 0; i < (N + 1); i++)
presum[i] = 0;
// Single state dynamic programming
// relation for prefix sum array
for(let i = 1; i <= N; i += 1)
{
presum[i] = presum[i - 1] + arr[i - 1];
}
// Modulo class vector
let moduloclass = new Array(N);
for(let i = 0; i < N; i += 1)
{
moduloclass[i] = [];
}
// Storing the index value
// in the modulo class vector
for(let i = 1; i <= N; i += 1)
{
moduloclass[presum[i] % N].push(i - 1);
}
// If there exists a sub-array with
// starting index equal to zero
if (moduloclass[0].length > 0)
{
document.write(0 + " " +
moduloclass[0][0]);
return;
}
for(let i = 1; i < N; i += 1)
{
// In this class, there are more than
// two presums%N. Hence difference of
// any two subarrays would be a multiple of N
if (moduloclass[i].length >= 2)
{
// 0 based indexing
document.write(moduloclass[i][0] + 1 +
" " + moduloclass[i][1]);
return;
}
}
}
// Driver code
let arr = [ 7, 3, 5, 2 ];
let N = arr.length;
CheckSubarray(arr, N);
// This code is contributed by unknown2108
</script>
Producción:
1 2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)