Dada una array de tamaño N y X. Encuentre los movimientos mínimos necesarios para hacer la array en orden creciente. En cada movimiento, uno puede agregar X a cualquier elemento de la array.
Ejemplos :
Input : a = { 1, 3, 3, 2 }, X = 2
Output : 3
Explanation : Modified array is { 1, 3, 5, 6 }
Input : a = { 3, 5, 6 }, X = 5
Output : 0
Observación :
Tomemos dos números a y b. a >= b y convertir esto en a < b agregando algún número X.
entonces, a < b + k*X
( a – b ) / x < k
entonces, el valor mínimo posible de k es ( a – b ) / x + 1.
Enfoque :
Iterate over the given array and take two numbers when a[i] >= a[i-1] and apply above observation.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find minimum moves required
// to make the array in increasing order
#include <bits/stdc++.h>
using namespace std;
// function to find minimum moves required
// to make the array in increasing order
int MinimumMoves(int a[], int n, int x)
{
// to store answer
int ans = 0;
// iterate over an array
for (int i = 1; i < n; i++) {
// non- increasing order
if (a[i] <= a[i - 1]) {
int p = (a[i - 1] - a[i]) / x + 1;
// add moves to answer
ans += p;
// increase the element
a[i] += p * x;
}
}
// return required answer
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 3, 2 };
int x = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout << MinimumMoves(arr, n, x);
return 0;
}
C
// C program to find minimum moves required
// to make the array in increasing order
#include <stdio.h>
// function to find minimum moves required
// to make the array in increasing order
int MinimumMoves(int a[], int n, int x)
{
// to store answer
int ans = 0;
// iterate over an array
for (int i = 1; i < n; i++) {
// non- increasing order
if (a[i] <= a[i - 1]) {
int p = (a[i - 1] - a[i]) / x + 1;
// add moves to answer
ans += p;
// increase the element
a[i] += p * x;
}
}
// return required answer
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 3, 2 };
int x = 2;
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d",MinimumMoves(arr, n, x));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program to find minimum moves required
// to make the array in increasing order
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
// function to find minimum moves required
// to make the array in increasing order
static int MinimumMoves(int a[], int n, int x)
{
// to store answer
int ans = 0;
// iterate over an array
for (int i = 1; i < n; i++) {
// non- increasing order
if (a[i] <= a[i - 1]) {
int p = (a[i - 1] - a[i]) / x + 1;
// add moves to answer
ans += p;
// increase the element
a[i] += p * x;
}
}
// return required answer
return ans;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 3, 3, 2 };
int x = 2;
int n = arr.length;
System.out.println(MinimumMoves(arr, n, x));
}
}
Python3
# Python3 program to find minimum # moves required to make the array # in increasing order # function to find minimum moves required # to make the array in increasing order def MinimumMoves(a, n, x) : # to store answer ans = 0 # iterate over an array for i in range(1, n) : # non- increasing order if a[i] <= a[i - 1] : p = (a[i - 1] - a[i]) // x + 1 # add moves to answer ans += p # increase the element a[i] += p * x # return required answer return ans # Driver code if __name__ == "__main__" : arr = [1, 3, 3, 2] x = 2 n = len(arr) print(MinimumMoves(arr, n, x)) # This code is contributed by ANKITRAI1
C#
// C# program to find minimum moves required
// to make the array in increasing order
using System;
class GFG {
// function to find minimum moves required
// to make the array in increasing order
static int MinimumMoves(int[] a, int n, int x)
{
// to store answer
int ans = 0;
// iterate over an array
for (int i = 1; i < n; i++) {
// non- increasing order
if (a[i] <= a[i - 1]) {
int p = (a[i - 1] - a[i]) / x + 1;
// add moves to answer
ans += p;
// increase the element
a[i] += p * x;
}
}
// return required answer
return ans;
}
// Driver code
public static void Main()
{
int[] arr = {1, 3, 3, 2};
int x = 2;
int n = arr.Length;
Console.Write(MinimumMoves(arr, n, x));
}
}
// This code is contributed by ChitraNayal
PHP
<?php
// PHP program to find minimum
// moves required to make the
// array in increasing order
// function to find minimum
// moves required to make the
// array in increasing order
function MinimumMoves(&$a, $n, $x)
{
// to store answer
$ans = 0;
// iterate over an array
for ($i = 1; $i < $n; $i++)
{
// non- increasing order
if ($a[$i] <= $a[$i - 1])
{
$p = ($a[$i - 1] - $a[$i]) / $x + 1;
// add moves to answer
$ans += $p;
// increase the element
$a[$i] += $p * $x;
}
}
// return required answer
return $ans;
}
// Driver code
$arr = array(1, 3, 3, 2 );
$x = 2;
$n = sizeof($arr);
echo ((int)MinimumMoves($arr, $n, $x));
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to find minimum
// moves required to make the array in
// increasing order
// Function to find minimum moves required
// to make the array in increasing order
function MinimumMoves(a, n, x)
{
// To store answer
var ans = 0;
// Tterate over an array
for(i = 1; i < n; i++)
{
// Non- increasing order
if (a[i] <= a[i - 1])
{
var p = parseInt((a[i - 1] -
a[i]) / x + 1);
// Add moves to answer
ans += p;
// Increase the element
a[i] += p * x;
}
}
// Return required answer
return ans;
}
// Driver code
var arr = [ 1, 3, 3, 2 ];
var x = 2;
var n = arr.length;
document.write(MinimumMoves(arr, n, x));
// This code is contributed by aashish1995
</script>
Producción:
3
Complejidad de tiempo: O(n), para iterar sobre la array donde n es el tamaño de la array
Espacio auxiliar: O(1), ya que no se requiere espacio adicional
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA