Dada una array arr[] con N elementos, la tarea es encontrar el número mínimo de operaciones requeridas para que se logre una progresión aritmética con los elementos de la array con una diferencia común de 1. En una sola operación, cualquier elemento puede incrementarse en 1 Ejemplos :
Entrada: arr[] = {4, 4, 5, 5, 7}
Salida: 5
La array deseada es {4, 5, 6, 7, 8} que
se puede lograr en el mínimo de operaciones posibles.
Entrada: arr[] = {11, 2, 5, 6}
Salida: 26
Dado que solo podemos hacer incrementos,
cambiamos la array a {11, 12, 13, 14}
Acercarse:
- Podemos utilizar la búsqueda binaria para resolver este problema.
- Construiremos la array deseada con el último elemento fijo que aumentará si la solución no es válida o disminuirá si es válida, al igual que en la búsqueda binaria.
- Verifique que todos los elementos de la array deseada sean mayores o iguales que la array de entrada para realizar operaciones en los elementos para que sean iguales a los elementos deseados. Encuentre el conteo de operaciones.
- Encuentre el valor mínimo posible del último elemento que satisfaga la condición de todos los elementos en la array deseada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that return true if the
// required array can be generated
// with m as the last element
bool check(int m, int n, int arr[])
{
// Build the desired array
int desired[n];
for (int i = n - 1; i >= 0; i--) {
desired[i] = m;
m--;
}
// Check if the given array can
// be converted to the desired array
// with the given operation
for (int i = 0; i < n; i++) {
if (arr[i] > desired[i] || desired[i] < 1) {
return false;
}
}
return true;
}
// Function to return the minimum number
// of operations required to convert the
// given array to an increasing AP series
// with common difference as 1
int minOperations(int arr[], int n)
{
int start = (int)arr[n - 1];
int end = *(max_element(arr, arr + n)) + n;
int max_arr = 0;
// Apply Binary Search
while (start <= end) {
int mid = (start + end) / 2;
// If array can be generated with
// mid as the last element
if (check(mid, n, arr)) {
// Current ans is mid
max_arr = mid;
// Check whether the same can be
// achieved with even less operations
end = mid - 1;
}
else {
start = mid + 1;
}
}
// Build the desired array
int desired[n];
for (int i = n - 1; i >= 0; i--) {
desired[i] = max_arr;
max_arr--;
}
// Calculate the number of
// operations required
int operations = 0;
for (int i = 0; i < n; i++) {
operations += (desired[i] - arr[i]);
}
// Return the number of
// operations required
return operations;
}
// Driver code
int main()
{
int arr[] = { 4, 4, 5, 5, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minOperations(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
class GFG
{
// Function that return true if the
// required array can be generated
// with m as the last element
static boolean check(int m, int n, int arr[])
{
// Build the desired array
int[] desired = new int[n];
for (int i = n - 1; i >= 0; i--)
{
desired[i] = m;
m--;
}
// Check if the given array can
// be converted to the desired array
// with the given operation
for (int i = 0; i < n; i++)
{
if (arr[i] > desired[i] || desired[i] < 1)
{
return false;
}
}
return true;
}
// Function to return the minimum number
// of operations required to convert the
// given array to an increasing AP series
// with common difference as 1
static int minOperations(int arr[], int n)
{
int start = (int) arr[n - 1];
int end = Arrays.stream(arr).max().getAsInt() + n;
int max_arr = 0;
// Apply Binary Search
while (start <= end)
{
int mid = (start + end) / 2;
// If array can be generated with
// mid as the last element
if (check(mid, n, arr))
{
// Current ans is mid
max_arr = mid;
// Check whether the same can be
// achieved with even less operations
end = mid - 1;
}
else
{
start = mid + 1;
}
}
// Build the desired array
int[] desired = new int[n];
for (int i = n - 1; i >= 0; i--)
{
desired[i] = max_arr;
max_arr--;
}
// Calculate the number of
// operations required
int operations = 0;
for (int i = 0; i < n; i++)
{
operations += (desired[i] - arr[i]);
}
// Return the number of
// operations required
return operations;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {4, 4, 5, 5, 7};
int n = arr.length;
System.out.println(minOperations(arr, n));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach # Function that return true if the # required array can be generated # with m as the last element def check( m, n, arr) : # Build the desired array desired = [0]*n; for i in range(n-1,-1,-1) : desired[i] = m; m -= 1; # Check if the given array can # be converted to the desired array # with the given operation for i in range(n) : if (arr[i] > desired[i] or desired[i] < 1) : return False; return True # Function to return the minimum number # of operations required to convert the # given array to an increasing AP series # with common difference as 1 def minOperations(arr, n) : start = arr[n - 1]; end = max(arr) + n; max_arr = 0; # Apply Binary Search while (start <= end) : mid = (start + end) // 2; # If array can be generated with # mid as the last element if (check(mid, n, arr)) : # Current ans is mid max_arr = mid; # Check whether the same can be # achieved with even less operations end = mid - 1; else : start = mid + 1; # Build the desired array desired = [0]* n; for i in range(n-1, -1,-1) : desired[i] = max_arr; max_arr -= 1; # Calculate the number of # operations required operations = 0; for i in range(n) : operations += (desired[i] - arr[i]); # Return the number of # operations required return operations; # Driver code if __name__ == "__main__" : arr = [ 4, 4, 5, 5, 7 ]; n = len(arr); print(minOperations(arr, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Linq;
class GFG
{
// Function that return true if the
// required array can be generated
// with m as the last element
static Boolean check(int m, int n, int []arr)
{
// Build the desired array
int[] desired = new int[n];
for (int i = n - 1; i >= 0; i--)
{
desired[i] = m;
m--;
}
// Check if the given array can
// be converted to the desired array
// with the given operation
for (int i = 0; i < n; i++)
{
if (arr[i] > desired[i] || desired[i] < 1)
{
return false;
}
}
return true;
}
// Function to return the minimum number
// of operations required to convert the
// given array to an increasing AP series
// with common difference as 1
static int minOperations(int []arr, int n)
{
int start = (int) arr[n - 1];
int end = arr.Max() + n;
int max_arr = 0;
// Apply Binary Search
while (start <= end)
{
int mid = (start + end) / 2;
// If array can be generated with
// mid as the last element
if (check(mid, n, arr))
{
// Current ans is mid
max_arr = mid;
// Check whether the same can be
// achieved with even less operations
end = mid - 1;
}
else
{
start = mid + 1;
}
}
// Build the desired array
int[] desired = new int[n];
for (int i = n - 1; i >= 0; i--)
{
desired[i] = max_arr;
max_arr--;
}
// Calculate the number of
// operations required
int operations = 0;
for (int i = 0; i < n; i++)
{
operations += (desired[i] - arr[i]);
}
// Return the number of
// operations required
return operations;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {4, 4, 5, 5, 7};
int n = arr.Length;
Console.WriteLine(minOperations(arr, n));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function that return true if the
// required array can be generated
// with m as the last element
function check(m, n, arr)
{
// Build the desired array
var desired = Array(n);
for (var i = n - 1; i >= 0; i--) {
desired[i] = m;
m--;
}
// Check if the given array can
// be converted to the desired array
// with the given operation
for (var i = 0; i < n; i++) {
if (arr[i] > desired[i] || desired[i] < 1) {
return false;
}
}
return true;
}
// Function to return the minimum number
// of operations required to convert the
// given array to an increasing AP series
// with common difference as 1
function minOperations(arr, n)
{
var start = arr[n - 1];
var end = arr.reduce((a,b)=> Math.max(a,b)) + n;
var max_arr = 0;
// Apply Binary Search
while (start <= end) {
var mid = parseInt((start + end) / 2);
// If array can be generated with
// mid as the last element
if (check(mid, n, arr)) {
// Current ans is mid
max_arr = mid;
// Check whether the same can be
// achieved with even less operations
end = mid - 1;
}
else {
start = mid + 1;
}
}
// Build the desired array
var desired = Array(n);
for (var i = n - 1; i >= 0; i--) {
desired[i] = max_arr;
max_arr--;
}
// Calculate the number of
// operations required
var operations = 0;
for (var i = 0; i < n; i++) {
operations += (desired[i] - arr[i]);
}
// Return the number of
// operations required
return operations;
}
// Driver code
var arr = [4, 4, 5, 5, 7 ];
var n = arr.length;
document.write( minOperations(arr, n));
</script>
Producción:
5