Given an unsorted array A[] of N integers and integer K, the task is to count the minimum number of times K should be added to the array elements to make the array sorted.
Examples:
Input: A[] = {2, 4, 3, 5, 9}, K = 3
Output: 2
Explanation: In the above array element at index 3 is 3 which is less than its previous element.
So, add K with the element and array becomes {2, 4, 6, 5, 9}.
Now element at index 4 is less than its previous so add K.
Final array {2, 4, 6, 8, 9} which is sorted.Input: A[] = {3, 6, 8, 5, 3}, K = 4
Output: 3
Explanation: Perform operation at index 4 once and twice at index 5.
Approach: The problem can be solved by using the following idea:
If the array element at index i is greater than that of the element at (i-1) then no addition is required. Otherwise, add K with the value at ith index until it is greater than the (i-1)th element.
Follow the steps to solve the problem:
- Create two pointers i and j , i starts from 0 and j from 1.
- Then run a while loop till i < N and j < N
- Check if arr[i] <= arr[j] or not if it is then simply increment both the pointers by 1.
- If arr[i] > arr[j] then add integer K to arr[j] until it become greater than or equal to arr[i] and for each addition of K, increment a count by 1 after that increment both the pointers by 1.
- Lastly, return the count.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to count min no of operationsint minOperation(vector<int> arr, int N, int K){ int i = 0, j = 1, count = 0; while (i < N && j < N) { // If current elements are sorted // Increment i and j by 1 if (arr[i] <= arr[j]) { i++; j++; } // If current elements are not // Sorted then add K to arr[j] till // It become greater than equal to // arr[i] and then increment // i and j by 1 else { while (arr[i] > arr[j]) { arr[j] += K; // Increment count in // Each operation count++; } i++; j++; } } return count;}// Driver Codeint main(){ vector<int> arr = { 3, 6, 8, 5, 3 }; int N = 5, K = 4; // Function call cout << minOperation(arr, N, K); return 0;} |
Java
// Java program for above approachimport java.util.*;class GFG{ // Function to count min no of operations static int minOperation(int[] arr, int N, int K) { int i = 0, j = 1, count = 0; while (i < N && j < N) { // If current elements are sorted // Increment i and j by 1 if (arr[i] <= arr[j]) { i++; j++; } // If current elements are not // Sorted then add K to arr[j] till // It become greater than equal to // arr[i] and then increment // i and j by 1 else { while (arr[i] > arr[j]) { arr[j] += K; // Increment count in // Each operation count++; } i++; j++; } } return count; } // Driver code public static void main(String[] args) { int[] arr = { 3, 6, 8, 5, 3 }; int N = 5, K = 4; // Function call System.out.print(minOperation(arr, N, K)); }}// This code is contributed by sanjoy_62. |
Python3
# python3 implementation of above approach# Function to count min no of operationsdef minOperation(arr, N, K): i, j, count = 0, 1, 0 while (i < N and j < N): # If current elements are sorted # Increment i and j by 1 if (arr[i] <= arr[j]): i += 1 j += 1 # If current elements are not # Sorted then add K to arr[j] till # It become greater than equal to # arr[i] and then increment # i and j by 1 else: while (arr[i] > arr[j]): arr[j] += K # Increment count in # Each operation count += 1 i += 1 j += 1 return count# Driver Codeif __name__ == "__main__": arr = [3, 6, 8, 5, 3] N, K = 5, 4 # Function call print(minOperation(arr, N, K))# This code is contributed by rakeshsahni |
C#
// C# implementation of above approachusing System;class GFG { // Function to count min no of operations static int minOperation(int[] arr, int N, int K) { int i = 0, j = 1, count = 0; while (i < N && j < N) { // If current elements are sorted // Increment i and j by 1 if (arr[i] <= arr[j]) { i++; j++; } // If current elements are not // Sorted then add K to arr[j] till // It become greater than equal to // arr[i] and then increment // i and j by 1 else { while (arr[i] > arr[j]) { arr[j] += K; // Increment count in // Each operation count++; } i++; j++; } } return count; } // Driver Code public static void Main() { int[] arr = { 3, 6, 8, 5, 3 }; int N = 5, K = 4; // Function call Console.Write(minOperation(arr, N, K)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach// Function to count min no of operationsfunction minOperation( arr, N, K){ let i = 0, j = 1, count = 0; while (i < N && j < N) { // If current elements are sorted // Increment i and j by 1 if (arr[i] <= arr[j]) { i++; j++; } // If current elements are not // Sorted then add K to arr[j] till // It become greater than equal to // arr[i] and then increment // i and j by 1 else { while (arr[i] > arr[j]) { arr[j] += K; // Increment count in // Each operation count++; } i++; j++; } } return count;}// Driver Code let arr = [3, 6, 8, 5, 3]; let N = 5, K = 4; // Function call document.write(minOperation(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
