Dado un arreglo arr[] de N enteros y un entero K , la tarea es encontrar la longitud del subarreglo más pequeño cuyo producto, cuando se divide por N , da el resto K. Si no existe tal subarreglo, imprime «-1» .
Ejemplos:
Entrada: N = 3, arr = {2, 2, 6}, K = 1
Salida: 2
Explicación:
Todos los subarreglos posibles son:
{2} -> 2(mod 3) = 2
{2} -> 2(mod 3 ) = 2
{6} -> 6(mod 3) = 0
{2, 2} -> (2 * 2)(mod 3) = 1
{2, 6} -> (2 * 6)(mod 3) = 0
{2, 2, 6} -> (2 * 2 * 6)(mod 3) = 0
Solo el subarreglo {2, 2} deja el resto K( = 1).
Por lo tanto, la longitud del subarreglo mínimo es 2.Entrada: N = 4, arr = {2, 2, 3, 3}, K = 1
Salida: 2
Explicación:
Solo el subarreglo {3, 3} satisface la propiedad, por lo que la longitud del subarreglo mínimo es 2.
Enfoque:
La idea es generar todos los subarreglos posibles del arreglo dado e imprimir la longitud del subarreglo más pequeño cuyo producto de todos los elementos da el resto K cuando se divide por N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the subarray of
// minimum length
int findsubArray(int arr[], int N, int K)
{
// Initialize the minimum
// subarray size to N + 1
int res = N + 1;
// Generate all possible subarray
for (int i = 0; i < N; i++) {
// Initialize the product
int curr_prod = 1;
for (int j = i; j < N; j++) {
// Find the product
curr_prod = curr_prod * arr[j];
if (curr_prod % N == K
&& res > (j - i + 1)) {
res = min(res, j - i + 1);
break;
}
}
}
// Return the minimum size of subarray
return (res == N + 1) ? 0 : res;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 2, 2, 3 };
int N = sizeof(arr)
/ sizeof(arr[0]);
int K = 1;
int answer = findsubArray(arr, N, K);
if (answer != 0)
cout << answer;
else
cout << "-1";
return 0;
}
Java
// Java program to implement the
// above approach
import java.util.*;
class GFG{
// Function to find the subarray of
// minimum length
static int findsubArray(int arr[],
int N, int K)
{
// Initialize the minimum
// subarray size to N + 1
int res = N + 1;
// Generate all possible subarray
for(int i = 0; i < N; i++)
{
// Initialize the product
int curr_prod = 1;
for(int j = i; j < N; j++)
{
// Find the product
curr_prod = curr_prod * arr[j];
if (curr_prod % N == K &&
res > (j - i + 1))
{
res = Math.min(res, j - i + 1);
break;
}
}
}
// Return the minimum size of subarray
return (res == N + 1) ? 0 : res;
}
// Driver code
public static void main(String[] args)
{
// Given array
int arr[] = { 2, 2, 3 };
int N = arr.length;
int K = 1;
int answer = findsubArray(arr, N, K);
if (answer != 0)
System.out.println(answer);
else
System.out.println("-1");
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # Function to find the subarray of # minimum length def findsubArray(arr, N, K): # Initialize the minimum # subarray size to N + 1 res = N + 1 # Generate all possible subarray for i in range(0, N): # Initialize the product curr_prad = 1 for j in range(i, N): # Find the product curr_prad = curr_prad * arr[j] if (curr_prad % N == K and res > (j - i + 1)): res = min(res, j - i + 1) break # Return the minimum size of subarray if res == N + 1: return 0 else: return res # Driver code if __name__ == '__main__': # Given array arr = [ 2, 2, 3 ] N = len(arr) K = 1 answer = findsubArray(arr, N, K) if (answer != 0): print(answer) else: print(-1) # This code is contributed by virusbuddah_
C#
// C# program to implement the
// above approach
using System;
class GFG{
// Function to find the subarray of
// minimum length
static int findsubArray(int []arr,
int N, int K)
{
// Initialize the minimum
// subarray size to N + 1
int res = N + 1;
// Generate all possible subarray
for(int i = 0; i < N; i++)
{
// Initialize the product
int curr_prod = 1;
for(int j = i; j < N; j++)
{
// Find the product
curr_prod = curr_prod * arr[j];
if (curr_prod % N == K &&
res > (j - i + 1))
{
res = Math.Min(res, j - i + 1);
break;
}
}
}
// Return the minimum size of subarray
return (res == N + 1) ? 0 : res;
}
// Driver code
public static void Main(String[] args)
{
// Given array
int []arr = { 2, 2, 3 };
int N = arr.Length;
int K = 1;
int answer = findsubArray(arr, N, K);
if (answer != 0)
Console.WriteLine(answer);
else
Console.WriteLine("-1");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript program to implement the
// above approach
// Function to find the subarray of
// minimum length
function findsubArray(arr, N, K)
{
// Initialize the minimum
// subarray size to N + 1
var res = N + 1;
// Generate all possible subarray
for(i = 0; i < N; i++)
{
// Initialize the product
var curr_prod = 1;
for(j = i; j < N; j++)
{
// Find the product
curr_prod = curr_prod * arr[j];
if (curr_prod % N == K &&
res > (j - i + 1))
{
res = Math.min(res, j - i + 1);
break;
}
}
}
// Return the minimum size of subarray
return (res == N + 1) ? 0 : res;
}
// Driver code
// Given array
var arr = [ 2, 2, 3 ];
var N = arr.length;
var K = 1;
var answer = findsubArray(arr, N, K);
if (answer != 0)
document.write(answer);
else
document.write("-1");
// This code is contributed by umadevi9616
</script>
Producción:
2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shivamsinghal1012 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA