Longitud del subarreglo más largo cuya suma no es divisible por el entero K

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:
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

Publicación traducida automáticamente

Artículo escrito por saltycode y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *