CSES Solutions – Increasing Array
Given an array arr[] of size N, you want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element. On each move, you may increase the value of any element by one. Find the minimum number of moves required.
Examples:
Input: N = 5, arr[] = {3, 2, 5, 1, 7}
Output: 5
Explanation:
- Increase arr[1] by 1, so arr[] becomes {3, 3, 5, 1, 7}.
- Increase arr[3] by 4, so arr[] becomes {3, 3, 5, 6, 7}.
Input: N = 3, arr[] = {1, 2, 3}
Output: 0
Explanation: No moves are needed as the array is already in increasing order.
Algorithm: To solve the problem, follow the below idea:
The problem can be solved by traversing the array and comparing each element with its previous element. If the current element is smaller than the previous element so we need to increase the current element till it becomes equal to the previous element. This can be done by applying increment operations (previous element – current element) number of times. Sum of all these operations will be the minimum number of moves required.
Step-by-step algorithm:
- Initialize a variable ans = 0 to store the minimum number of moves.
- Start a loop from the second element of the array.
- For every element, if the previous element is greater than the current element, then add (previous element – current element) to ans and update the current element = previous element.
- After iterating over all the elements, return ans.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function to find the minimum number of moves
ll solve(ll* arr, ll N)
{
// variable to store the final answer
ll ans = 0;
// Iterate over all the elements and compare them with
// the previous element
for (ll i = 1; i < N; i++) {
if (arr[i - 1] > arr[i]) {
ans += (arr[i - 1] - arr[i]);
arr[i] = arr[i - 1];
}
}
return ans;
}
int main()
{
// Sample Input
ll N = 5;
ll arr[N] = { 3, 2, 5, 1, 7 };
cout << solve(arr, N) << "\n";
return 0;
}
import java.util.Arrays;
public class Main {
// Function to find the minimum number of moves
static long solve(long[] arr, int N)
{
// variable to store the final answer
long ans = 0;
// Iterate over all the elements and compare them
// with the previous element
for (int i = 1; i < N; i++) {
if (arr[i - 1] > arr[i]) {
ans += (arr[i - 1] - arr[i]);
arr[i] = arr[i - 1];
}
}
return ans;
}
public static void main(String[] args)
{
// Sample Input
int N = 5;
long[] arr = { 3, 2, 5, 1, 7 };
System.out.println(solve(arr, N));
}
}
// This code is contributed by rambabuguphka
# Function to find the minimum number of moves
def solve(arr, N):
# variable to store the final answer
ans = 0
# Iterate over all the elements and compare them with
# the previous element
for i in range(1, N):
if arr[i - 1] > arr[i]:
ans += (arr[i - 1] - arr[i])
arr[i] = arr[i - 1]
return ans
def main():
# Sample Input
N = 5
arr = [3, 2, 5, 1, 7]
print(solve(arr, N))
if __name__ == "__main__":
main()
using System;
class GFG {
// Function to find the minimum number of moves
static long Solve(long[] arr, long N) {
// Variable to store the final answer
long ans = 0;
// Iterate over all the elements and compare them with
// previous element
for (long i = 1; i < N; i++) {
if (arr[i - 1] > arr[i]) {
ans += (arr[i - 1] - arr[i]);
arr[i] = arr[i - 1];
}
}
return ans;
}
public static void Main(string[] args) {
// Sample Input
long N = 5;
long[] arr = { 3, 2, 5, 1, 7 };
// Call the Solve function and
// print the result
Console.WriteLine(Solve(arr, N));
}
}
// Function to find the minimum number of moves
function solve(arr, N) {
// variable to store the final answer
let ans = 0;
// Iterate over all the elements and compare them
// with the previous element
for (let i = 1; i < N; i++) {
if (arr[i - 1] > arr[i]) {
ans += (arr[i - 1] - arr[i]);
arr[i] = arr[i - 1];
}
}
return ans;
}
// Main function
function main() {
// Sample Input
const N = 5;
const arr = [3, 2, 5, 1, 7];
// Call the solve function and print the result
console.log(solve(arr, N));
}
// Call the main function to execute the program
main();
Output
5
Time Complexity: O(N), where N is the size of input array arr[].
Auxiliary Space: O(1)
Contact Us