Dada una array , arr[] de tamaño N y un número entero K , la tarea es encontrar la longitud de la subsecuencia más larga de la array dada de modo que la diferencia absoluta de cada par en la subsecuencia sea divisible por K.
Ejemplos:
Entrada: arr[] = {10, 12, 16, 20, 32, 15}, K = 4
Salida: 4
Explicación:
La subsecuencia más larga en la que la diferencia absoluta de cada par divisible por K (= 4) es {12, 26, 20, 32}.
Por lo tanto, la salida requerida es 4Entrada: arr[] = {12, 3, 13, 5, 21, 11}, K = 3
Salida: 3
Enfoque ingenuo : el enfoque más simple para resolver este problema es generar todas las subsecuencias posibles de la array dada e imprimir la longitud de la subsecuencia más larga que tenga una diferencia absoluta de cada par divisible por K.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente : para optimizar el enfoque anterior, la idea es utilizar Hashing en función de la siguiente observación:
La diferencia absoluta de todos los pares posibles de un subconjunto que tiene el mismo valor de arr[i] % K debe ser divisible por K.
Prueba matemática:
Si arr[i] % K = arr[j] % K
=> abs(arr[i] – arr[j]) % K debe ser 0.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos hash[K] para almacenar la frecuencia de arr[i] % K .
- Recorra la array hash[] y encuentre el elemento máximo en la array hash[] .
- Finalmente, imprima el elemento máximo de la array hash[] .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length
// of subsequence that satisfy
// the given condition
int maxLenSub(int arr[],
int N, int K)
{
// Store the frequencies
// of arr[i] % K
int hash[K];
// Initialize hash[] array
memset(hash, 0, sizeof(hash));
// Traverse the given array
for (int i = 0; i < N; i++) {
// Update frequency of
// arr[i] % K
hash[arr[i] % K]++;
}
// Stores the length of
// the longest subsequence that
// satisfy the given condition
int LenSub = 0;
// Find the maximum element
// in hash[] array
for (int i = 0; i < K; i++) {
LenSub = max(LenSub, hash[i]);
}
return LenSub;
}
// Driver Code
int main()
{
int arr[] = { 12, 3, 13, 5, 21, 11 };
int K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxLenSub(arr, N, K);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the length
// of subsequence that satisfy
// the given condition
static int maxLenSub(int arr[],
int N, int K)
{
// Store the frequencies
// of arr[i] % K
int []hash = new int[K];
// Traverse the given array
for (int i = 0; i < N; i++)
{
// Update frequency of
// arr[i] % K
hash[arr[i] % K]++;
}
// Stores the length of
// the longest subsequence that
// satisfy the given condition
int LenSub = 0;
// Find the maximum element
// in hash[] array
for (int i = 0; i < K; i++)
{
LenSub = Math.max(LenSub,
hash[i]);
}
return LenSub;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {12, 3, 13, 5, 21, 11};
int K = 3;
int N = arr.length;
System.out.print(maxLenSub(arr, N, K));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to implement # the above approach # Function to find the length # of subsequence that satisfy # the given condition def maxLenSub(arr, N, K): # Store the frequencies # of arr[i] % K hash = [0] * K # Traverse the given array for i in range(N): # Update frequency of # arr[i] % K hash[arr[i] % K] += 1 # Stores the length of the # longest subsequence that # satisfy the given condition LenSub = 0 # Find the maximum element # in hash[] array for i in range(K): LenSub = max(LenSub, hash[i]) return LenSub # Driver Code if __name__ == '__main__': arr = [ 12, 3, 13, 5, 21, 11 ] K = 3 N = len(arr) print(maxLenSub(arr, N, K)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the length
// of subsequence that satisfy
// the given condition
static int maxLenSub(int []arr,
int N, int K)
{
// Store the frequencies
// of arr[i] % K
int []hash = new int[K];
// Traverse the given array
for (int i = 0; i < N; i++)
{
// Update frequency of
// arr[i] % K
hash[arr[i] % K]++;
}
// Stores the length of
// the longest subsequence that
// satisfy the given condition
int LenSub = 0;
// Find the maximum element
// in hash[] array
for (int i = 0; i < K; i++)
{
LenSub = Math.Max(LenSub,
hash[i]);
}
return LenSub;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {12, 3, 13,
5, 21, 11};
int K = 3;
int N = arr.Length;
Console.Write(maxLenSub(arr, N, K));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the length
// of subsequence that satisfy
// the given condition
function maxLenSub(arr, N, K)
{
// Store the frequencies
// of arr[i] % K
let hash = Array.from({length: K}, (_, i) => 0);
// Traverse the given array
for(let i = 0; i < N; i++)
{
// Update frequency of
// arr[i] % K
hash[arr[i] % K]++;
}
// Stores the length of
// the longest subsequence that
// satisfy the given condition
let LenSub = 0;
// Find the maximum element
// in hash[] array
for(let i = 0; i < K; i++)
{
LenSub = Math.max(LenSub,
hash[i]);
}
return LenSub;
}
// Driver Code
let arr = [ 12, 3, 13, 5, 21, 11 ];
let K = 3;
let N = arr.length;
document.write(maxLenSub(arr, N, K));
// This code is contributed by target_2
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(K)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA