Dada una array arr[] de longitud N y un número entero K , la tarea es encontrar la subarreglo más larga con una diferencia entre dos valores distintos iguales a K . Imprime la longitud del subarreglo más largo obtenido. De lo contrario, si no se obtiene dicho subarreglo, imprima -1 .
Ejemplos:
Entrada: arr[] = {0, 0, 1, 1, 3, 3, 3}, K = 1
Salida: 4
Explicación:
El subarreglo {0, 0, 1, 1} es el único subarreglo que tiene diferencia entre dos valores distintos iguales a K( = 1). Por lo tanto, la longitud es igual a 4.Entrada: arr[] = {5, 7, 1, 1, 2, 4, 4, 4, 5, 5, 4, 5, 8, 9}, K = 1
Salida: 7
Explicación:
Subarreglos {1, 1, 2}, {4, 4, 4, 5, 5, 4, 5} y {8, 9} son el único subarreglo que tiene una diferencia entre dos valores distintos iguales a K( = 1).
El subarreglo más largo entre ellos es {4, 4, 4, 5, 5, 4, 5}.
Por lo tanto, la longitud es 7.
Enfoque ingenuo:
- Una solución simple es considerar todos los subarreglos uno por uno y encontrar los subarreglos que contienen solo dos valores distintos y la diferencia entre esos dos valores es K . Continúe actualizando la longitud máxima del subarreglo obtenido.
- Finalmente imprima la longitud máxima obtenida.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente:
se puede observar que para que cualquier subarreglo consista en elementos con la diferencia entre dos elementos para ser exactamente K, el subarreglo debe constar de solo dos valores distintos. Por lo tanto, el enfoque anterior se puede optimizar aún más utilizando set para encontrar el subarreglo más largo que tenga solo dos valores distintos con una diferencia K. Siga los pasos a continuación para resolver el problema:
- Inicie el primer subarreglo desde el índice inicial del arreglo.
- Inserte ese elemento en el conjunto. Continúe con el siguiente elemento y verifique si este elemento es el mismo que el anterior o si tiene una diferencia absoluta de K.
- Si es así, inserte ese elemento en el conjunto y continúe aumentando la longitud del subarreglo. Una vez que se encuentra un tercer elemento distinto, compare la longitud del subarreglo actual con la longitud máxima del subarreglo y actualice en consecuencia.
- Actualice el nuevo elemento obtenido en el conjunto y proceda a repetir los pasos anteriores.
- Una vez recorrida toda la array, imprima la longitud máxima obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// longest subarray consisting of
// only two values with difference K
#include <bits/stdc++.h>
using namespace std;
// Function to return the length
// of the longest sub-array
int longestSubarray(int arr[], int n,
int k)
{
int i, j, Max = 1;
// Initialize set
set<int> s;
for (i = 0; i < n - 1; i++) {
// Store 1st element of
// sub-array into set
s.insert(arr[i]);
for (j = i + 1; j < n; j++) {
// Check absolute difference
// between two elements
if (abs(arr[i] - arr[j]) == 0
|| abs(arr[i] - arr[j]) == k) {
// If the new element is not
// present in the set
if (!s.count(arr[j])) {
// If the set contains
// two elements
if (s.size() == 2)
break;
// Otherwise
else
s.insert(arr[j]);
}
}
else
break;
}
if (s.size() == 2) {
// Update the maximum
// length
Max = max(Max, j - i);
// Remove the set
// elements
s.clear();
}
else
s.clear();
}
return Max;
}
// Driver Code
int main()
{
int arr[] = { 1, 0, 2, 2, 5, 5, 5 };
int N = sizeof(arr)
/ sizeof(arr[0]);
int K = 1;
int length = longestSubarray(
arr, N, K);
if (length == 1)
cout << -1;
else
cout << length;
return 0;
}
Java
// Java implementation to find the
// longest subarray consisting of
// only two values with difference K
import java.util.*;
class GFG{
// Function to return the length
// of the longest sub-array
static int longestSubarray(int arr[], int n,
int k)
{
int i, j, Max = 1;
// Initialize set
HashSet<Integer> s = new HashSet<Integer>();
for(i = 0; i < n - 1; i++)
{
// Store 1st element of
// sub-array into set
s.add(arr[i]);
for(j = i + 1; j < n; j++)
{
// Check absolute difference
// between two elements
if (Math.abs(arr[i] - arr[j]) == 0 ||
Math.abs(arr[i] - arr[j]) == k)
{
// If the new element is not
// present in the set
if (!s.contains(arr[j]))
{
// If the set contains
// two elements
if (s.size() == 2)
break;
// Otherwise
else
s.add(arr[j]);
}
}
else
break;
}
if (s.size() == 2)
{
// Update the maximum
// length
Max = Math.max(Max, j - i);
// Remove the set
// elements
s.clear();
}
else
s.clear();
}
return Max;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 0, 2, 2, 5, 5, 5 };
int N = arr.length;
int K = 1;
int length = longestSubarray(arr, N, K);
if (length == 1)
System.out.print(-1);
else
System.out.print(length);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation to find the
# longest subarray consisting of
# only two values with difference K
# Function to return the length
# of the longest sub-array
def longestSubarray (arr, n, k):
Max = 1
# Initialize set
s = set()
for i in range(n - 1):
# Store 1st element of
# sub-array into set
s.add(arr[i])
for j in range(i + 1, n):
# Check absolute difference
# between two elements
if (abs(arr[i] - arr[j]) == 0 or
abs(arr[i] - arr[j]) == k):
# If the new element is not
# present in the set
if (not arr[j] in s):
# If the set contains
# two elements
if (len(s) == 2):
break
# Otherwise
else:
s.add(arr[j])
else:
break
if (len(s) == 2):
# Update the maximum length
Max = max(Max, j - i)
# Remove the set elements
s.clear()
else:
s.clear()
return Max
# Driver Code
if __name__ == '__main__':
arr = [ 1, 0, 2, 2, 5, 5, 5 ]
N = len(arr)
K = 1
length = longestSubarray(arr, N, K)
if (length == 1):
print("-1")
else:
print(length)
# This code is contributed by himanshu77
C#
// C# implementation to find the
// longest subarray consisting of
// only two values with difference K
using System;
using System.Collections.Generic;
class GFG{
// Function to return the length
// of the longest sub-array
static int longestSubarray(int []arr, int n,
int k)
{
int i, j, Max = 1;
// Initialize set
HashSet<int> s = new HashSet<int>();
for(i = 0; i < n - 1; i++)
{
// Store 1st element of
// sub-array into set
s.Add(arr[i]);
for(j = i + 1; j < n; j++)
{
// Check absolute difference
// between two elements
if (Math.Abs(arr[i] - arr[j]) == 0 ||
Math.Abs(arr[i] - arr[j]) == k)
{
// If the new element is not
// present in the set
if (!s.Contains(arr[j]))
{
// If the set contains
// two elements
if (s.Count == 2)
break;
// Otherwise
else
s.Add(arr[j]);
}
}
else
break;
}
if (s.Count == 2)
{
// Update the maximum
// length
Max = Math.Max(Max, j - i);
// Remove the set
// elements
s.Clear();
}
else
s.Clear();
}
return Max;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 0, 2, 2, 5, 5, 5 };
int N = arr.Length;
int K = 1;
int length = longestSubarray(arr, N, K);
if (length == 1)
Console.Write(-1);
else
Console.Write(length);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation to find the
// longest subarray consisting of
// only two values with difference K
// Function to return the length
// of the longest sub-array
function longestSubarray(arr, n, k)
{
let i, j, Max = 1;
// Initialize set
let s = new Set();
for (i = 0; i < n - 1; i++) {
// Store 1st element of
// sub-array into set
s.add(arr[i]);
for (j = i + 1; j < n; j++) {
// Check absolute difference
// between two elements
if (Math.abs(arr[i] - arr[j]) == 0
|| Math.abs(arr[i] - arr[j]) == k) {
// If the new element is not
// present in the set
if (!s.has(arr[j])) {
// If the set contains
// two elements
if (s.size == 2)
break;
// Otherwise
else
s.add(arr[j]);
}
}
else
break;
}
if (s.size == 2) {
// Update the maximum
// length
Max = Math.max(Max, j - i);
// Remove the set
// elements
s.clear;
}
else
s.clear;
}
return Max;
}
let arr = [ 1, 0, 2, 2, 5, 5, 5 ];
let N = arr.length;
let K = 1;
let length = longestSubarray(arr, N, K);
if (length == 1)
document.write(-1);
else
document.write(length);
// This code is contributed by decode2207.
</script>
2
Complejidad de Tiempo: O(N 2 * logN)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por tanmaythole y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA