Dada una array arr[] de tamaño N , la tarea es encontrar el rango de valor mínimo [L, R] tal que:
- La array se puede dividir en K sub-arrays.
- Los elementos dentro del rango [L, R] son mayores que los elementos que están fuera del rango [l, r].
Ejemplos:
Entrada: arr[] = {1, 2, 2, 2}, K = 2
Salida: 2 2
Explicación: [2, 2] es el rango con la distancia mínima que puede dividir la array en dos subarreglos como
{1, 2, 2} -> dentro del rango = 2, fuera del rango =1
{2} -> dentro del rango =1, fuera del rango = 0.
En el 2 se divide el número de elementos dentro del rango > fuera del rango.Entrada: arr[] = {1, 2, 3, 4}, K = 3
Salida: 1 4
Explicación: [1, 4] es el rango con la distancia mínima porque la array se puede dividir en 3 subarreglos como
{1, 2 } -> dentro del rango = 2, fuera del rango =1,
{3} -> dentro del rango =1, fuera del rango = 0,
{4} -> dentro del rango = 1, fuera del rango = 0.
En las 3 divisiones, el número de elementos dentro del rango > fuera del rango.
Enfoque ingenuo: esto se puede hacer verificando los rangos de cada tamaño desde 1 hasta el tamaño de la array, luego verificando la cantidad de elementos en el rango y la cantidad de elementos fuera del rango, luego verificando si su diferencia es mayor que o igual a k.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: este enfoque se basa en una búsqueda binaria del rango [1, N] con técnica Hashing y suma de prefijos para realizar un seguimiento de la cantidad de elementos en la array que están en el rango hasta i y verificar si existe una posibilidad para cualquier rango que pueda dividir la array en K sub-arrays que siguen la condición dada. Siga los pasos mencionados:
- Inicialice el vector de conteo para almacenar las frecuencias de los elementos de la array.
- Inicialice una suma de prefijos vectoriales para almacenar el número de elementos hasta ese índice.
- Ahora recorra la array desde [1, N] y almacene el recuento de elementos hasta i usando la técnica de suma de prefijos.
- Inicialice can= 0, y l, r para almacenar el rango y low = 0, high = N para realizar una búsqueda binaria sobre el tamaño del rango.
- Realice una búsqueda binaria mientras bajo ≤ alto.
- Inicializa mid como (low + high)/2 .
- Iterar usando el ciclo for de [1, N-mid+1] usando i para verificar qué rango de tamaño es medio.
- Ahora cuente la cantidad de elementos en el rango [i, i+mid-1] y fuera del rango.
- Compruebe si la diferencia de los elementos dentro y fuera del rango es mayor o igual a K .
- Almacene el rango en l, r y haga can =1 si es mayor que igual a K .
- Si existe la posibilidad, suba hasta mediados de 1
- De lo contrario , bajo = medio +1 .
- Imprime el rango.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to minimize the range
// To divide the array arr
// Into k subarrays that has
// Number of elements in the range
// Greater than out of range
void find_minrange(vector<int> arr, int n, int k)
{
// Initialize the count vector
// To store the frequencies
// Of the elements
vector<int> count(n + 1);
for (auto x : arr)
count[x]++;
// Initialize a vector prefix sum to
// Store the number of elements till
// That index
vector<int> prefixsum(n + 1);
// Now traverse through from[1, n]
// And store the count of elements till i
for (int i = 1; i <= n; i++)
prefixsum[i] = prefixsum[i - 1]
+ count[i];
int low = 1, high = n;
// Initialize l, r to store the range
int l, r;
while (low <= high) {
// Initialize the mid
int mid = (low + high) / 2;
bool can = false;
// For each range size (mid)
for (int i = 1; i <= n - mid + 1; i++) {
// Count the number of elements
// In the range [i, i+mid-1]
// And out of the range
int inrange
= prefixsum[i + mid - 1]
- prefixsum[i - 1];
int outrange = n - inrange;
// Check if the difference of inrange
// And outrange is greater than
// or equal to k
if (inrange - outrange >= k) {
// Store the range
// Since it is a possible range
can = true;
l = i;
r = i + mid - 1;
break;
}
}
// If we have a possible range
// Minimize it
if (can) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
// Print the range
cout << l << " " << r;
}
// Driver Code
int main()
{
// Initialize the array arr[]
vector<int> arr = { 1, 2, 2, 2 };
int K = 2;
int N = arr.size();
// Function call
find_minrange(arr, N, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to minimize the range
// To divide the array arr
// Into k subarrays that has
// Number of elements in the range
// Greater than out of range
static void find_minrange(int[] arr, int n, int k)
{
// Initialize the count vector
// To store the frequencies
// Of the elements
int[] count = new int[n + 1];
for (int i = 0; i < arr.length; i++)
count[arr[i]]++;
// Initialize a vector prefix sum to
// Store the number of elements till
// That index
int[] prefixsum = new int[n + 1];
// Now traverse through from[1, n]
// And store the count of elements till i
for (int i = 1; i <= n; i++)
prefixsum[i] = prefixsum[i - 1] + count[i];
int low = 1, high = n;
// Initialize l, r to store the range
int l = 0, r = 0;
while (low <= high) {
// Initialize the mid
int mid = (low + high) / 2;
boolean can = false;
// For each range size (mid)
for (int i = 1; i <= n - mid + 1; i++) {
// Count the number of elements
// In the range [i, i+mid-1]
// And out of the range
int inrange = prefixsum[i + mid - 1]
- prefixsum[i - 1];
int outrange = n - inrange;
// Check if the difference of inrange
// And outrange is greater than
// or equal to k
if (inrange - outrange >= k) {
// Store the range
// Since it is a possible range
can = true;
l = i;
r = i + mid - 1;
break;
}
}
// If we have a possible range
// Minimize it
if (can == true) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
// Print the range
System.out.print(l + " " + r);
}
// Driver Code
public static void main(String args[])
{
// Initialize the array arr[]
int[] arr = { 1, 2, 2, 2 };
int K = 2;
int N = arr.length;
// Function call
find_minrange(arr, N, K);
}
}
// This code is contributed by code_hunt.
Python3
# python3 code for the above approach
# Function to minimize the range
# To divide the array arr
# Into k subarrays that has
# Number of elements in the range
# Greater than out of range
def find_minrange(arr, n, k):
# Initialize the count vector
# To store the frequencies
# Of the elements
count = [0 for _ in range(n + 1)]
for x in arr:
count[x] += 1
# Initialize a vector prefix sum to
# Store the number of elements till
# That index
prefixsum = [0 for _ in range(n + 1)]
# Now traverse through from[1, n]
# And store the count of elements till i
for i in range(1, n+1):
prefixsum[i] = prefixsum[i - 1] + count[i]
low, high = 1, n
# Initialize l, r to store the range
l, r = 0, 0
while (low <= high):
# Initialize the mid
mid = (low + high) // 2
can = False
# For each range size (mid)
for i in range(1, n - mid + 1 + 1):
# Count the number of elements
# In the range [i, i+mid-1]
# // And out of the range
inrange = prefixsum[i + mid - 1] - prefixsum[i - 1]
outrange = n - inrange
# Check if the difference of inrange
# And outrange is greater than
# or equal to k
if (inrange - outrange >= k):
# Store the range
# Since it is a possible range
can = True
l = i
r = i + mid - 1
break
# If we have a possible range
# Minimize it
if (can):
high = mid - 1
else:
low = mid + 1
# Print the range
print(f"{l} {r}")
# Driver Code
if __name__ == "__main__":
# Initialize the array arr[]
arr = [1, 2, 2, 2]
K = 2
N = len(arr)
# Function call
find_minrange(arr, N, K)
# This code is contributed by rakeshsahni
C#
// C# code for the above approach
using System;
class GFG {
// Function to minimize the range
// To divide the array arr
// Into k subarrays that has
// Number of elements in the range
// Greater than out of range
static void find_minrange(int[] arr, int n, int k)
{
// Initialize the count vector
// To store the frequencies
// Of the elements
int[] count = new int[n + 1];
for (int i = 0; i < arr.Length; i++)
count[arr[i]]++;
// Initialize a vector prefix sum to
// Store the number of elements till
// That index
int[] prefixsum = new int[n + 1];
// Now traverse through from[1, n]
// And store the count of elements till i
for (int i = 1; i <= n; i++)
prefixsum[i] = prefixsum[i - 1] + count[i];
int low = 1, high = n;
// Initialize l, r to store the range
int l = 0, r = 0;
while (low <= high) {
// Initialize the mid
int mid = (low + high) / 2;
bool can = false;
// For each range size (mid)
for (int i = 1; i <= n - mid + 1; i++) {
// Count the number of elements
// In the range [i, i+mid-1]
// And out of the range
int inrange = prefixsum[i + mid - 1]
- prefixsum[i - 1];
int outrange = n - inrange;
// Check if the difference of inrange
// And outrange is greater than
// or equal to k
if (inrange - outrange >= k) {
// Store the range
// Since it is a possible range
can = true;
l = i;
r = i + mid - 1;
break;
}
}
// If we have a possible range
// Minimize it
if (can == true) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
// Print the range
Console.Write(l + " " + r);
}
// Driver Code
public static void Main()
{
// Initialize the array arr[]
int[] arr = { 1, 2, 2, 2 };
int K = 2;
int N = arr.Length;
// Function call
find_minrange(arr, N, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to minimize the range
// To divide the array arr
// Into k subarrays that has
// Number of elements in the range
// Greater than out of range
function find_minrange(arr,n,k)
{
// Initialize the count vector
// To store the frequencies
// Of the elements
let count = new Array(n + 1).fill(0);
for (let x of arr)
count[x]++;
// Initialize a vector prefix sum to
// Store the number of elements till
// That index
let prefixsum = new Array(n + 1).fill(0);
// Now traverse through from[1, n]
// And store the count of elements till i
for (let i = 1; i <= n; i++)
prefixsum[i] = prefixsum[i - 1]
+ count[i];
let low = 1, high = n;
// Initialize l, r to store the range
let l, r;
while (low <= high) {
// Initialize the mid
let mid = Math.floor((low + high) / 2);
let can = false;
// For each range size (mid)
for (let i = 1; i <= n - mid + 1; i++) {
// Count the number of elements
// In the range [i, i+mid-1]
// And out of the range
let inrange
= prefixsum[i + mid - 1]
- prefixsum[i - 1];
let outrange = n - inrange;
// Check if the difference of inrange
// And outrange is greater than
// or equal to k
if (inrange - outrange >= k) {
// Store the range
// Since it is a possible range
can = true;
l = i;
r = i + mid - 1;
break;
}
}
// If we have a possible range
// Minimize it
if (can) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
// Print the range
document.write(l + " " + r);
}
// Driver Code
// Initialize the array arr[]
let arr = [ 1, 2, 2, 2 ];
let K = 2;
let N = arr.length;
// Function call
find_minrange(arr, N, K);
// This code is contributed by shinjanpatra
</script>
Producción
2 2
Complejidad de tiempo: O(N* log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA