Dado un arreglo arr[] de tamaño N y un entero k , nuestra tarea es encontrar la longitud del subarreglo más largo cuya suma de elementos no sea divisible por k. Si no existe tal subarreglo, devuelva -1.
Ejemplos:
Entrada: arr[] = {8, 4, 3, 1, 5, 9, 2}, k = 2
Salida: 5
Explicación:
El subarreglo es {8, 4, 3, 1, 5} con suma = 21, es no divisible por 2.
Entrada: arr[] = {6, 3, 12, 15}, k = 3
Salida: -1
Explicación:
No hay subarreglo que no sea divisible por 3.
Enfoque ingenuo: la idea es considerar todos los subarreglos y devolver la longitud del subarreglo más largo de modo que la suma de sus elementos no sea divisible por k .
Complejidad temporal: O(N 2 )
Espacio auxiliar: O(N)
Enfoque eficiente: La observación principal es que eliminar un elemento que es divisible por k no contribuirá a la solución, pero si eliminamos un elemento que no es divisible por k entonces la suma no sería divisible por k.
- Por lo tanto, permita que el no múltiplo de k más a la izquierda esté en el índice izquierdo , y que el no múltiplo de k más a la derecha esté en el índice derecho .
- Elimine los elementos de prefijo hasta el índice a la izquierda o el elemento de sufijo hasta el índice a la derecha y elimine los elementos que tienen una menor cantidad de elementos.
- Hay dos casos de esquina en este problema. Primero, si todos los elementos de la array son divisibles por k, entonces no existe tal subarreglo, por lo que devuelve -1. En segundo lugar, si la suma de todo el arreglo no es divisible por k, entonces el subarreglo será el arreglo mismo, así que devuelva el tamaño del arreglo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the length of
// the longest subarray whose sum is
// not divisible by integer K
#include <bits/stdc++.h>
using namespace std;
// Function to find the longest subarray
// with sum is not divisible by k
int MaxSubarrayLength(int arr[], int n, int k)
{
// left is the index of the
// leftmost element that is
// not divisible by k
int left = -1;
// right is the index of the
// rightmost element that is
// not divisible by k
int right;
// sum of the array
int sum = 0;
for (int i = 0; i < n; i++) {
// Find the element that
// is not multiple of k
if ((arr[i] % k) != 0) {
// left = -1 means we are
// finding the leftmost
// element that is not
// divisible by k
if (left == -1) {
left = i;
}
// Updating the
// rightmost element
right = i;
}
// update the sum of the
// array up to the index i
sum += arr[i];
}
// Check if the sum of the
// array is not divisible
// by k, then return the
// size of array
if ((sum % k) != 0) {
return n;
}
// All elements of array
// are divisible by k,
// then no such subarray
// possible so return -1
else if (left == -1) {
return -1;
}
else {
// length of prefix elements
// that can be removed
int prefix_length = left + 1;
// length of suffix elements
// that can be removed
int suffix_length = n - right;
// Return the length of
// subarray after removing
// the elements which have
// lesser number of elements
return n - min(prefix_length,
suffix_length);
}
}
// Driver Code
int main()
{
int arr[] = { 6, 3, 12, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 3;
cout << MaxSubarrayLength(arr, n, K);
return 0;
}
Java
// Java program to find the length of
// the longest subarray whose sum is
// not divisible by integer K
import java.util.*;
class GFG{
// Function to find the longest subarray
// with sum is not divisible by k
static int MaxSubarrayLength(int arr[], int n,
int k)
{
// left is the index of the
// leftmost element that is
// not divisible by k
int left = -1;
// right is the index of the
// rightmost element that is
// not divisible by k
int right = 0;
// sum of the array
int sum = 0;
for(int i = 0; i < n; i++)
{
// Find the element that
// is not multiple of k
if ((arr[i] % k) != 0)
{
// left = -1 means we are
// finding the leftmost
// element that is not
// divisible by k
if (left == -1)
{
left = i;
}
// Updating the
// rightmost element
right = i;
}
// Update the sum of the
// array up to the index i
sum += arr[i];
}
// Check if the sum of the
// array is not divisible
// by k, then return the
// size of array
if ((sum % k) != 0)
{
return n;
}
// All elements of array
// are divisible by k,
// then no such subarray
// possible so return -1
else if (left == -1)
{
return -1;
}
else
{
// Length of prefix elements
// that can be removed
int prefix_length = left + 1;
// Length of suffix elements
// that can be removed
int suffix_length = n - right;
// Return the length of
// subarray after removing
// the elements which have
// lesser number of elements
return n - Math.min(prefix_length,
suffix_length);
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 6, 3, 12, 15 };
int n = arr.length;
int K = 3;
System.out.println(MaxSubarrayLength(arr, n, K));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the length of # the longest subarray whose sum is # not divisible by integer # Function to find the longest subarray # with sum is not divisible by k def MaxSubarrayLength(arr, n, k): # left is the index of the # leftmost element that is # not divisible by k left = -1 # sum of the array sum = 0 for i in range(n): # Find the element that # is not multiple of k if ((arr[i] % k) != 0): # left = -1 means we are # finding the leftmost # element that is not # divisible by k if (left == -1): left = i # Updating the # rightmost element right = i # Update the sum of the # array up to the index i sum += arr[i] # Check if the sum of the # array is not divisible # by k, then return the # size of array if ((sum % k) != 0): return n # All elements of array # are divisible by k, # then no such subarray # possible so return -1 elif(left == -1): return -1 else: # length of prefix elements # that can be removed prefix_length = left + 1 # length of suffix elements # that can be removed suffix_length = n - right # Return the length of # subarray after removing # the elements which have # lesser number of elements return n - min(prefix_length, suffix_length) # Driver Code if __name__ == "__main__": arr = [ 6, 3, 12, 15 ] n = len(arr) K = 3 print(MaxSubarrayLength(arr, n, K)) # This code is contributed by chitranayal
C#
// C# program to find the length of
// the longest subarray whose sum is
// not divisible by integer K
using System;
class GFG{
// Function to find the longest subarray
// with sum is not divisible by k
static int MaxSubarrayLength(int []arr, int n,
int k)
{
// left is the index of the
// leftmost element that is
// not divisible by k
int left = -1;
// right is the index of the
// rightmost element that is
// not divisible by k
int right = 0;
// sum of the array
int sum = 0;
for(int i = 0; i < n; i++)
{
// Find the element that
// is not multiple of k
if ((arr[i] % k) != 0)
{
// left = -1 means we are
// finding the leftmost
// element that is not
// divisible by k
if (left == -1)
{
left = i;
}
// Updating the
// rightmost element
right = i;
}
// Update the sum of the
// array up to the index i
sum += arr[i];
}
// Check if the sum of the
// array is not divisible
// by k, then return the
// size of array
if ((sum % k) != 0)
{
return n;
}
// All elements of array
// are divisible by k,
// then no such subarray
// possible so return -1
else if (left == -1)
{
return -1;
}
else
{
// Length of prefix elements
// that can be removed
int prefix_length = left + 1;
// Length of suffix elements
// that can be removed
int suffix_length = n - right;
// Return the length of
// subarray after removing
// the elements which have
// lesser number of elements
return n - Math.Min(prefix_length,
suffix_length);
}
}
// Driver code
public static void Main(string[] args)
{
int []arr = { 6, 3, 12, 15 };
int n = arr.Length;
int K = 3;
Console.Write(MaxSubarrayLength(arr, n, K));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to find the length of
// the longest subarray whose sum is
// not divisible by integer K
// Function to find the longest subarray
// with sum is not divisible by k
function MaxSubarrayLength(arr, n, k)
{
// left is the index of the
// leftmost element that is
// not divisible by k
let left = -1;
// right is the index of the
// rightmost element that is
// not divisible by k
let right = 0;
// sum of the array
let sum = 0;
for(let i = 0; i < n; i++)
{
// Find the element that
// is not multiple of k
if ((arr[i] % k) != 0)
{
// left = -1 means we are
// finding the leftmost
// element that is not
// divisible by k
if (left == -1)
{
left = i;
}
// Updating the
// rightmost element
right = i;
}
// Update the sum of the
// array up to the index i
sum += arr[i];
}
// Check if the sum of the
// array is not divisible
// by k, then return the
// size of array
if ((sum % k) != 0)
{
return n;
}
// All elements of array
// are divisible by k,
// then no such subarray
// possible so return -1
else if (left == -1)
{
return -1;
}
else
{
// Length of prefix elements
// that can be removed
let prefix_length = left + 1;
// Length of suffix elements
// that can be removed
let suffix_length = n - right;
// Return the length of
// subarray after removing
// the elements which have
// lesser number of elements
return n - Math.min(prefix_length,
suffix_length);
}
}
// Driver Code
let arr = [ 6, 3, 12, 15 ];
let n = arr.length;
let K = 3;
document.write(MaxSubarrayLength(arr, n, K));
// This code is contributed by target_2.
</script>
Producción:
-1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array