Dados dos números enteros N y K , la tarea es comprobar si es posible formar una permutación de N números enteros tal que contenga al menos 1 subarreglo tal que el producto de la longitud de ese subarreglo con el elemento mínimo presente en él sea K .
Una permutación de tamaño N tiene todos los números enteros del 1 al N presentes solo una vez.
Ejemplos:
Entrada: N = 5, K = 6
Salida: Verdadero
Explicación: {4, 2, 1, 3, 5} es un arreglo válido que contiene números enteros del 1 al 5. El subarreglo requerido es {3, 5}.
Longitud del subarreglo = 2, elemento mínimo en el subarreglo = 3.
Su producto = 2 x 3 = 6, que es igual a K.Entrada: N = 4, K = 10
Salida: Falso
Planteamiento: El problema se puede resolver con base en la siguiente observación:
Supongamos que en un arreglo de tamaño N que tiene números enteros de 1 a N , existe un subarreglo de tamaño L , que tiene un elemento mínimo M tal que M * L = K. Por lo tanto, M = K / L o K debe ser divisible por la longitud del subarreglo Además, M debe ser el elemento mínimo en el subarreglo de tamaño L .
En una permutación de N enteros, hay N – M + 1 elementos, que son mayores o iguales que M. Entonces, para que M sea mínimo en un subarreglo de tamaño L, N – M + 1 ≥ L
Siga los pasos mencionados a continuación para implementar la idea anterior:
- Iterar la array de i = 1 a N
- Sea i la longitud del subarreglo que satisface las condiciones requeridas.
- Calcular el elemento mínimo en el subarreglo.
- Como, L * M = K , entonces, M=K / L , (donde M es el elemento mínimo en el subarreglo actual)
- Compruebe si las condiciones establecidas en la observación se cumplen o no, es decir , M < N – L + 1 .
- Si es así, devuelve verdadero.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;
// Function toCheck if there can be
// a subarray such that product of its
// length with its minimum element is K
bool isPossible(int N, int K)
{
// Variable to store answer
bool ans = true;
for (int i = 1; i <= N; i++) {
// Variable to store length of
// current candidate subarray
int length = i;
// Since minimum element * length
// of subarray should be K,
// that means K should be divisible
// by length of candidate subarray
if (K % length == 0) {
// Candidate for minimum element
int min_element = K / length;
// Checking if candidate for
// minimum element can actually
// be a minimum element in a
// sequence on size "length"
if (min_element < N - length + 1) {
ans = true;
break;
}
}
}
// Returning answer
return ans;
}
// Driver code
int main()
{
int N = 5;
int K = 6;
// Function call
bool answer = isPossible(N, K);
cout << boolalpha << answer;
return 0;
}
Java
// JAVA code for above approach
import java.util.*;
class GFG
{
// Function toCheck if there can be
// a subarray such that product of its
// length with its minimum element is K
public static boolean isPossible(int N, int K)
{
// Variable to store answer
boolean ans = true;
for (int i = 1; i <= N; i++) {
// Variable to store length of
// current candidate subarray
int length = i;
// Since minimum element * length
// of subarray should be K,
// that means K should be divisible
// by length of candidate subarray
if (K % length == 0) {
// Candidate for minimum element
int min_element = K / length;
// Checking if candidate for
// minimum element can actually
// be a minimum element in a
// sequence on size "length"
if (min_element < N - length + 1) {
ans = true;
break;
}
}
}
// Returning answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 5;
int K = 6;
// Function call
boolean answer = isPossible(N, K);
System.out.print(answer);
}
}
// This code is contributed by Taranpreet
Python3
# Python3 code for above approach # Function toCheck if there can be # a subarray such that product of its # length with its minimum element is K def isPossible(N, K): # Variable to store answer ans = 1 for i in range(1, N + 1): # Variable to store length of # current candidate subarray length = i # Since minimum element * length # of subarray should be K, # that means K should be divisible # by length of candidate subarray if (K % length == 0): # Candidate for minimum element min_element = K / length # Checking if candidate for # minimum element can actually # be a minimum element in a # sequence on size "length" if (min_element < N - length + 1): ans = 1 break # Returning answer return ans # Driver code if __name__ == "__main__": N = 5 K = 6 # Function call answer = isPossible(N, K) print(bool(answer)) # This code is contributed by hrithikgarg03188.
C#
// C# code for above approach
using System;
class GFG {
// Function toCheck if there can be
// a subarray such that product of its
// length with its minimum element is K
static bool isPossible(int N, int K)
{
// Variable to store answer
bool ans = true;
for (int i = 1; i <= N; i++) {
// Variable to store length of
// current candidate subarray
int length = i;
// Since minimum element * length
// of subarray should be K,
// that means K should be divisible
// by length of candidate subarray
if (K % length == 0) {
// Candidate for minimum element
int min_element = K / length;
// Checking if candidate for
// minimum element can actually
// be a minimum element in a
// sequence on size "length"
if (min_element < N - length + 1) {
ans = true;
break;
}
}
}
// Returning answer
return ans;
}
// Driver code
public static void Main()
{
int N = 5;
int K = 6;
// Function call
bool answer = isPossible(N, K);
Console.Write(answer);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function toCheck if there can be
// a subarray such that product of its
// length with its minimum element is K
function isPossible(N, K)
{
// Variable to store answer
let ans = true;
for (let i = 1; i <= N; i++) {
// Variable to store length of
// current candidate subarray
let length = i;
// Since minimum element * length
// of subarray should be K,
// that means K should be divisible
// by length of candidate subarray
if (K % length == 0) {
// Candidate for minimum element
let min_element = Math.floor(K / length);
// Checking if candidate for
// minimum element can actually
// be a minimum element in a
// sequence on size "length"
if (min_element < N - length + 1) {
ans = true;
break;
}
}
}
// Returning answer
return ans;
}
// Driver code
let N = 5;
let K = 6;
// Function call
let ans = isPossible(N, K);
document.write(ans)
// This code is contributed by Potta Lokesh
</script>
true
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA