Dada una array arr[] que consta de N enteros, la tarea es encontrar el número mínimo de elementos de la array que deben cambiarse a cualquier número entero arbitrario de modo que la diferencia entre el elemento de la array máximo y mínimo sea ( N – 1) y todos los elementos de la array debe ser distinto .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 5, 6}
Salida: 1
Explicación:
Cambie 6->4, la array final será {1, 2, 3, 5, 4} y la diferencia es igual a 5 – 1 = 4.Entrada: arr[] = {1, 10, 100, 1000}
Salida: 3
Enfoque: El problema dado se puede resolver utilizando la técnica de clasificación y ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Ordena la array en orden no decreciente .
- Mantener una variable ans e inicializarla con valor N que almacenará la mínima respuesta posible.
- Elimina todos los elementos duplicados de la array dada arr[] .
- Itere sobre el rango [0, M) donde M es el nuevo tamaño de la array después de eliminar los duplicados usando la variable i y realice las siguientes tareas:
- Atraviese un ciclo while hasta que j sea menor que M y A[j] sea menor que igual a A[i] + N – 1 y aumente el valor de j en 1 .
- Actualice el valor de ans al mínimo de ans y (N – j + i) .
- Después de realizar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum changes
// needed to make difference of maximum
// and minimum element as (N - 1)
int minOperations(vector<int>& A)
{
int N = A.size();
// Stores the resultant count
int ans = N;
// Maintain a pointer j that will
// denote the rightmost position of
// the valid array
int j = 0;
// Sort the array
sort(begin(A), end(A));
// Only keep unique elements
A.erase(unique(begin(A), end(A)),
end(A));
// Store the new size of the array
// after removing duplicates
int M = A.size();
// IterM;ate over the range
for (int i = 0; i < M; ++i) {
while (j < M && A[j] <= A[i] + N - 1) {
++j;
}
// Check minimum over this
// starting point
ans = min(ans, N - j + i);
// The length of this subarray
// is `j - i`. Replace `N - j + i`
// elements to make it good
}
return ans;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 10, 100, 1000 };
cout << minOperations(arr);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
import java.util.*;
class GFG {
// Function to find the minimum changes
// needed to make difference of maximum
// and minimum element as (N - 1)
public static int minOperations(int[] A) {
int N = A.length;
// Stores the resultant count
int ans = N;
// Maintain a pointer j that will
// denote the rightmost position of
// the valid array
int j = 0;
// Sort the array
Arrays.sort(A);
// Only keep unique elements
removeDups(A);
// Store the new size of the array
// after removing duplicates
int M = A.length;
// IterM;ate over the range
for (int i = 0; i < M; ++i) {
while (j < M && A[j] <= A[i] + N - 1) {
++j;
}
// Check minimum over this
// starting point
ans = Math.min(ans, N - j + i);
// The length of this subarray
// is `j - i`. Replace `N - j + i`
// elements to make it good
}
return ans;
}
public static void removeDups(int[] a) {
LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();
// adding elements to LinkedHashSet
for (int i = 0; i < a.length; i++)
set.add(a[i]);
}
// Driver Code
public static void main(String args[]) {
int[] arr = { 1, 10, 100, 1000 };
System.out.println(minOperations(arr));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python 3 program for the above approach # Function to find the minimum changes # needed to make difference of maximum # and minimum element as (N - 1) def minOperations(A): N = len(A) # Stores the resultant count ans = N # Maintain a pointer j that will # denote the rightmost position of # the valid array j = 0 # Sort the array A.sort() # Only keep unique elements A = list(set(A)) # Store the new size of the array # after removing duplicates A.sort() M = len(A) # IterM;ate over the range for i in range(M): while (j < M and A[j] <= A[i] + N - 1): j += 1 # Check minimum over this # starting point ans = min(ans, N - j + i) # The length of this subarray # is `j - i`. Replace `N - j + i` # elements to make it good return ans # Driver Code if __name__ == '__main__': arr = [1, 10, 100, 1000] print(minOperations(arr)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the minimum changes
// needed to make difference of maximum
// and minimum element as (N - 1)
public static int minOperations(int[] A) {
int N = A.Length;
// Stores the resultant count
int ans = N;
// Maintain a pointer j that will
// denote the rightmost position of
// the valid array
int j = 0;
// Sort the array
Array.Sort(A);
// Only keep unique elements
removeDups(A);
// Store the new size of the array
// after removing duplicates
int M = A.Length;
// IterM;ate over the range
for (int i = 0; i < M; ++i) {
while (j < M && A[j] <= A[i] + N - 1) {
++j;
}
// Check minimum over this
// starting point
ans = Math.Min(ans, N - j + i);
// The length of this subarray
// is `j - i`. Replace `N - j + i`
// elements to make it good
}
return ans;
}
public static void removeDups(int[] a) {
HashSet<int> set = new HashSet<int>();
// adding elements to LinkedHashSet
for (int i = 0; i < a.Length; i++)
set.Add(a[i]);
}
// Driver Code
public static void Main() {
int[] arr = { 1, 10, 100, 1000 };
Console.Write(minOperations(arr));
}
}
// This code is contributed by saurabh_jaiswal.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum changes
// needed to make difference of maximum
// and minimum element as (N - 1)
function minOperations(A)
{
let N = A.length;
// Stores the resultant count
let ans = N;
// Maintain a pointer j that will
// denote the rightmost position of
// the valid array
let j = 0;
// Sort the array
A.sort(function (a, b) { return a - b });
// Only keep unique elements
let unique_A = [];
for (let i = 0; i < A.length - 1; i++) {
if (A[i] != A[i + 1]) {
unique_A.push(A[i])
}
}
A = unique_A;
// Store the new size of the array
// after removing duplicates
let M = A.length;
// Iterate over the range
for (let i = 0; i < M; ++i) {
while (j < M && A[j] <= A[i] + N - 1) {
++j;
}
// Check minimum over this
// starting point
ans = Math.min(ans, N - j + i);
// The length of this subarray
// is `j - i`. Replace `N - j + i`
// elements to make it good
}
return ans;
}
// Driver Code
let arr = [1, 10, 100, 1000];
document.write(minOperations(arr));
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA