Subarreglo más largo con suma divisible por K

Dado un arr[] que contiene n enteros y un entero positivo k . El problema es encontrar la longitud del subarreglo más largo con la suma de los elementos divisible por el valor k dado .

Ejemplos:

Entrada: arr[] = {2, 7, 6, 1, 4, 5}, k = 3
Salida: 4
Explicación: El subarreglo es {7, 6, 1, 4} con suma 18, que es divisible por 3 .

Entrada: arr[] = {-2, 2, -5, 12, -11, -1, 7}, k = 3
Salida: 5

Método 1 (enfoque ingenuo): Considere todos los subarreglos y devuelva la longitud del subarreglo con una suma divisible por k que tenga la longitud más larga. 
Complejidad Temporal: O(n ² ).

Método 2 (enfoque eficiente): cree una array mod_arr[] donde mod_arr[i] almacena (sum(arr[0]+arr[1]..+arr[i]) % k) . Cree una tabla hash que tenga una tupla como (ele, i) , donde ele representa un elemento de mod_arr[] e i representa el índice del elemento de la primera aparición en mod_arr[] . Ahora, recorra mod_arr[] de i = 0 a n y siga los pasos que se indican a continuación.

1. Si mod_arr[i] == 0, actualice max_len = ( i + 1).
2. De lo contrario, si mod_arr[i] no está presente en la tabla hash, cree una tupla (mod_arr[i], i) en la tabla hash.
3. De lo contrario, obtenga el valor de la tabla hash asociado con mod_arr[i]. Deja que esto sea yo .
4. Si maxLen < (i – idx), actualice max_len = (i – idx).
5. Finalmente, devuelva max_len .

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation to find the longest subarray
// with sum divisible by k
 
#include <bits/stdc++.h>
using namespace std;
 
// function to find the longest subarray
// with sum divisible by k
 
int longestSubarrWthSumDivByK(int arr[], int n, int k)
{
    // unordered map 'um' implemented as
    // hash table
    unordered_map<int, int> um;
     
    // 'mod_arr[i]' stores (sum[0..i] % k)
    int mod_arr[n], max_len = 0;
    int curr_sum = 0;
     
    // traverse arr[] and build up the
    // array 'mod_arr[]'
    for (int i = 0; i < n; i++)
    {
        curr_sum += arr[i];
         
        // as the sum can be negative, taking modulo twice
        mod_arr[i] = ((curr_sum % k) + k) % k;       
 
        // if true then sum(0..i) is divisible by k
        if (mod_arr[i] == 0)
            // update 'max'
            max_len = i + 1;
         
        // if value 'mod_arr[i]' not present in 'um'
        // then store it in 'um' with index of its
        // first occurrence       
        else if (um.find(mod_arr[i]) == um.end())
            um[mod_arr[i]] = i;
             
        else
            // if true, then update 'max'
            if (max_len < (i - um[mod_arr[i]]))
                max_len = i - um[mod_arr[i]];           
    }
     
    // return the required length of longest subarray
    // with sum divisible by 'k'
    return max_len;
}                         
 
// Driver code
int main()
{
    int arr[] = {2, 7, 6, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
     
    cout << "Length = "
         << longestSubarrWthSumDivByK(arr, n, k);
          
    return 0;    
}
 
// Code updated by Kshitij Dwivedi

// Java implementation to find the longest
// subarray with sum divisible by k
import java.io.*;
import java.util.*;
 
class GfG {
         
    // function to find the longest subarray
    // with sum divisible by k
    static int longestSubarrWthSumDivByK(int arr[], int n, int k)
    {
        // unordered map 'um' implemented as
        // hash table
        HashMap<Integer, Integer> um= new HashMap<Integer, Integer>();
         
        // 'mod_arr[i]' stores (sum[0..i] % k)
        int mod_arr[]= new int[n];
        int max_len = 0;
        int curr_sum = 0;
         
        // traverse arr[] and build up the
        // array 'mod_arr[]'
        for (int i = 0; i < n; i++)
        {
            curr_sum += arr[i];
             
            // as the sum can be negative,
            // taking modulo twice
            mod_arr[i] = ((curr_sum % k) + k) % k;    
 
            // if true then sum(0..i) is
            // divisible by k
            if (mod_arr[i] == 0)
                // update 'max'
                max_len = i + 1;
             
            // if value 'mod_arr[i]' not present in 'um'
            // then store it in 'um' with index of its
            // first occurrence    
            else if (um.containsKey(mod_arr[i]) == false)
                um.put(mod_arr[i] , i);
                 
            else
                // if true, then update 'max'
                if (max_len < (i - um.get(mod_arr[i])))
                    max_len = i - um.get(mod_arr[i]);        
        }
         
        // return the required length of longest subarray
        // with sum divisible by 'k'
        return max_len;
    }   
     
    public static void main (String[] args)
    {
        int arr[] = {2, 7, 6, 1, 4, 5};
        int n = arr.length;
        int k = 3;
         
        System.out.println("Length = "+
                            longestSubarrWthSumDivByK(arr, n, k));
         
    }
}
 
// This code is contributed by Gitanjali, updated by Kshitij Dwivedi

# Python3 implementation to find the
# longest subarray with sum divisible by k
 
# Function to find the longest
# subarray with sum divisible by k
 
def longestSubarrWthSumDivByK(arr, n, k):
     
    # unordered map 'um' implemented
    # as hash table
    um = {}
 
    # 'mod_arr[i]' stores (sum[0..i] % k)
    mod_arr = [0 for i in range(n)]
    max_len = 0
    curr_sum = 0
     
    # Traverse arr[] and build up
    # the array 'mod_arr[]'
    for i in range(n):
        curr_sum += arr[i]
         
        # As the sum can be negative,
        # taking modulo twice
        mod_arr[i] = ((curr_sum % k) + k) % k
 
        # If true then sum(0..i) is
        # divisible by k
        if (mod_arr[i] == 0):
             
            # Update 'max_len'
            max_len = i + 1
         
        # If value 'mod_arr[i]' not present in
        # 'um' then store it in 'um' with index
        # of its first occurrence
        elif (mod_arr[i] not in um):
            um[mod_arr[i]] = i
             
        else:
              # If true, then update 'max_len'
            if (max_len < (i - um[mod_arr[i]])):
                max_len = i - um[mod_arr[i]]        
     
    # Return the required length of longest subarray
    # with sum divisible by 'k'
    return max_len   
 
# Driver Code
if __name__ == '__main__':
     
    arr = [2, 7, 6, 1, 4, 5]
    n = len(arr)
    k = 3
     
    print("Length =",
           longestSubarrWthSumDivByK(arr, n, k))
     
# This code is contributed by Surendra_Gangwar, updated by Kshitij Dwivedi

using System;
using System.Collections.Generic;
 
// C# implementation to find the longest 
// subarray with sum divisible by k
 
public class GfG
{
 
    // function to find the longest subarray
    // with sum divisible by k
    public static int longestSubarrWthSumDivByK(int[] arr, int n, int k)
    {
        // unordered map 'um' implemented as
        // hash table
        Dictionary<int, int> um = new Dictionary<int, int>();
 
        // 'mod_arr[i]' stores (sum[0..i] % k)
        int[] mod_arr = new int[n];
        int max_len = 0;
        int curr_sum = 0;
 
        // traverse arr[] and build up the
        // array 'mod_arr[]'
        for (int i = 0; i < n; i++)
        {
            curr_sum += arr[i];
 
            // as the sum can be negative, 
            // adjusting and calculating modulo twice
            mod_arr[i] = ((curr_sum % k) + k) % k;
 
            // if true then sum(0..i) is 
            // divisible by k
            if (mod_arr[i] == 0)
            {
                // update 'max_len'
                max_len = i + 1;
            }
 
            // if value 'mod_arr[i]' not present in 'um'
            // then store it in 'um' with index of its
            // first occurrence     
            else if (um.ContainsKey(mod_arr[i]) == false)
            {
                um[mod_arr[i]] = i;
            }
 
            else
            {
                // if true, then update 'max_len'
                if (max_len < (i - um[mod_arr[i]]))
                {
                    max_len = i - um[mod_arr[i]];
                }
            }
        }
 
        // return the required length of longest subarray with
        // sum divisible by 'k'
        return max_len;
    }
 
    public static void Main(string[] args)
    {
        int[] arr = new int[] {2, 7, 6, 1, 4, 5};
        int n = arr.Length;
        int k = 3;
 
        Console.WriteLine("Length = " + longestSubarrWthSumDivByK(arr, n, k));
 
    }
}
 
// This code is contributed by Shrikant13, updated by Kshitij Dwivedi

<script>
 
// Javascript implementation to find the longest subarray
// with sum divisible by k
 
// function to find the longest subarray
// with sum divisible by k
function longestSubarrWthSumDivByK(arr, n, k)
{
    // unordered map 'um' implemented as
    // hash table
    var um = new Map();
     
    // 'mod_arr[i]' stores (sum[0..i] % k)
    var mod_arr = Array(n), max_len = 0;
    var curr_sum = 0;
     
    // traverse arr[] and build up the
    // array 'mod_arr[]'
    for (var i = 0; i < n; i++)
    {
        curr_sum += arr[i];
         
        // as the sum can be negative, taking modulo twice
        mod_arr[i] = ((curr_sum % k) + k) % k;       
 
        // if true then sum(0..i) is divisible
        // by k
        if (mod_arr[i] == 0)
            // update 'max_len'
            max_len = i + 1;
         
        // if value 'mod_arr[i]' not present in 'um'
        // then store it in 'um' with index of its
        // first occurrence       
        else if (!um.has(mod_arr[i]))
            um.set(mod_arr[i] , i);
             
        else
            // if true, then update 'max_len'
            if (max_len < (i - um.get(mod_arr[i])))
                max_len = i - um.get(mod_arr[i]);           
    }
     
    // return the required length of longest subarray with
    // sum divisible by 'k'
    return max_len;
}                         
 
// Driver program to test above
var arr = [2, 7, 6, 1, 4, 5];
var n = arr.length;
var k = 3;
 
document.write( "Length = "
     + longestSubarrWthSumDivByK(arr, n, k));
      
// This code is contributed by rrrtnx, and updated by Kshitij Dwivedi
</script>

Length = 4

Complejidad de tiempo: O(n) , ya que recorremos la array de entrada solo una vez.
Espacio auxiliar: O(n * k) , O(n) para mod_arr[] y O(k) para almacenar los valores restantes en la tabla hash.

Enfoque optimizado para el espacio: la optimización del espacio para el enfoque anterior de O(n) En lugar de mantener una array separada para almacenar el módulo de todos los valores, lo calculamos sobre la marcha y almacenamos los restos en la tabla hash.

A continuación se muestra la implementación:

#include <bits/stdc++.h>
 
using namespace std;
 
// function to find the longest subarray
// with sum divisible by k
int longestSubarrWthSumDivByK(int arr[], int n, int k)
{
    // unordered map 'um' implemented as
    // hash table
    unordered_map<int, int> um;
 
    int max_len = 0;
    int curr_sum = 0;
 
    for (int i = 0; i < n; i++)
    {
        curr_sum += arr[i];
 
        int mod = ((curr_sum % k) + k) % k;
       
        // if true then sum(0..i) is divisible
        // by k
        if (mod == 0)
            // update 'max_len'
            max_len = i + 1;
 
        // if value 'mod_arr[i]' not present in 'um'
        // then store it in 'um' with index of its
        // first occurrence
        else if (um.find(mod) == um.end())
            um[mod] = i;
 
        else
            // if true, then update 'max_len'
            if (max_len < (i - um[mod]))
                max_len = i - um[mod];
    }
 
    // return the required length of longest subarray with
    // sum divisible by 'k'
    return max_len;
}
 
// Driver code
int main()
{
    int arr[] = {2, 7, 6, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
 
    cout << "Length = " << longestSubarrWthSumDivByK(arr, n, k);
 
    return 0;
}
 
// Code Updated by Kshitij Dwivedi

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
class GFG {
    static int longestSubarrWthSumDivByK(int arr[], int n, int k)
    {
        Map<Integer, Integer> map = new HashMap<>();
       
        int max_len = 0;
        int sum = 0;
       
        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
           
            // to handle negavtive values as well
            int mod = ((sum % k) + k) % k;
 
            if (mod == 0)
                max_len = i + 1;
 
            if (!map.containsKey(mod))
                map.put(mod, i);
            else
            {
                int sz = i - map.get(mod);
                max_len = Math.max(max_len, sz);
            }
        }
 
        return max_len;
    }
 
    public static void main(String[] args)
    {
        int arr[] = {2, 7, 6, 1, 4, 5};
        int n = arr.length;
        int k = 3;
 
        System.out.println("Length = " + longestSubarrWthSumDivByK(arr, n, k));
    }
}
 
// Updated By Kshitij Dwivedi

# function to find the longest subarray
#  with sum divisible by k
def longestSubarrWthSumDivByK(arr, n, k):
   
    # unordered map 'um' implemented as
    # hash table
    um = {}
 
    max_len = 0
    curr_sum = 0
 
    for i in range(n):
       
        curr_sum += arr[i]
        mod = ((curr_sum % k) + k) % k
        # if true then sum(0..i) is divisible by k
         
        if mod == 0:
            # update 'max_len'
            max_len = i + 1
             
        # if value 'mod_arr[i]' not present in 'um'
        # then store it in 'um' with index of its
        # first occurrence
        elif mod in um.keys():
            if max_len < (i - um[mod]):
                max_len = i - um[mod]
 
        else:
            um[mod] = i
 
    # return the required length of longest subarray with
    # sum divisible by 'k'
    return max_len
   
arr = [2, 7, 6, 1, 4, 5]
n = len(arr)
k = 3
print("Length =", longestSubarrWthSumDivByK(arr, n, k))
 
# This code is contributed by amreshkumar3, and updated by Kshitij Dwivedi

using System;
using System.Collections.Generic;
 
// C# implementation to find the longest
// subarray with sum divisible by k
public class GFG {
 
    public static int longestSubarrWthSumDivByK(int[] arr,
                                             int n, int k)
    {
        // unordered map 'um' implemented as
        // hash table
        Dictionary<int, int> um = new Dictionary<int, int>();
 
        int max_len = 0;
        int curr_sum = 0;
 
        for (int i = 0; i < n; i++)
        {
            curr_sum += arr[i];
 
            int mod = ((curr_sum % k) + k) % k;
           
            // if true then sum(0..i) is divisible
            // by k
            if (mod == 0)   
            // update 'max_len'
            {
                max_len = i + 1;
            }
 
            // if value 'mod' not present in 'um'
            // then store it in 'um' with index of its
            // first occurrence
            else if (um.ContainsKey(mod) == false)
            {
                um[mod] = i;
            }
 
            else
            {
                  // if true, then update 'max'
                if (max_len < (i - um[mod]))
                {
                    max_len = i - um[mod];
                }
            }
        }
        // return the required length of longest subarray with
        // sum divisible by 'k'
        return max_len;
    }
   
    public static void Main(string[] args)
    {
        int[] arr = new int[] {2, 7, 6, 1, 4, 5};
        int n = arr.Length;
        int k = 3;
 
        Console.WriteLine("Length = " + longestSubarrWthSumDivByK(arr, n, k));
    }
}
 
// This code is contributed by ishankhandelwals and updated by Kshitij Dwivedi

<script>
// function to find the longest subarray
// with sum divisible by k
function longestSubarrWthSumDivByK(arr,n,k)
{
    // map 'um' implemented as
    // hash table
    let um = new Map();
 
    let max_len = 0;
    let curr_sum = 0;
 
    for (let i = 0; i < n; i++)
    {
        curr_sum += arr[i];
 
        let mod = ((curr_sum % k) + k) % k;
        // if true then sum(0..i) is divisible
        // by k
        if (mod == 0)
            // update 'max_len'
            max_len = i + 1;
 
        // if value 'mod_arr[i]' not present in 'um'
        // then store it in 'um' with index of its
        // first occurrence
        else if (um.has(mod) == false)
            um.set(mod,i);
 
        else
            // if true, then update 'max'
            if (max_len < (i - um.get(mod)))
            max_len = i - um.get(mod);
    }
 
    // required length of longest subarray with
    // sum divisible by 'k'
    return max;
}
 
// Driver program to test above
 
let arr = [2, 7, 6, 1, 4, 5];
let n = arr.length;
let k = 3;
 
document.write("Length = " + longestSubarrWthSumDivByK(arr, n, k));
 
// This code is contributed by shinjanpatra, and updated by Kshitij Dwivedi.
</script>

Length = 4

Complejidad de tiempo: O(n) , ya que recorremos la array de entrada solo una vez.
Espacio Auxiliar: O(n)