Given an integer N and two arrays increasing[] and decreasing[], such that they have elements from 1 to N only. The task is to find the minimum number of steps for each element of the two arrays to reach either 0 or N. A step is defined as follows:
- In one step, all the elements of the increasing[] array increases by 1, and all the elements of the decreasing[] array decreases by 1.
- When an element becomes either 0 or N, no more increase or decrease operation is performed on it.
Examples:
Input: N = 5, increasing[] = {1, 2}, decreasing[] = {3, 4}Â
Output: 4
Explanation:Â
Step 1: increasing[] array becomes {2, 3}, decreasing[] = {2, 3}Â
Step 2: increasing[] array becomes {3, 4}, decreasing[] = {1, 2}Â
Step 3: increasing[] array becomes {4, 5}, decreasing[] = {0, 1}Â
Step 4: increasing[] array becomes {5, 5}, decreasing[] = {0, 0}Â
4 Steps are required for all elements to become either 0 or N. Hence, the output is 4.Input: N = 7, increasing[] = {3, 5}, decreasing[] = {6}Â
Output: 6
Approach: The idea is to find the maximum between the steps required by all the elements of the increasing[] array and the decreasing[] array to reach N and 0 respectively. Below are the steps:
- Find the minimum element of the array increasing[].
- The maximum steps taken by all the elements of the increasing[] array to reach N is given by N – min(increasing[]).
- Find the maximum element of the array decreasing[].
- The maximum steps taken by all the elements of the decreasing[] array to reach 0 is given by max(decreasing[]).
- Therefore, the minimum number of steps when all the elements become either 0 or N is given by max(N – min(increasing[]), max(decreasing[])).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h> using namespace std;Â
// Function that finds the minimum // steps to reach either 0 or N for // given increasing and decreasing // arrays void minSteps(int N, int increasing[], Â Â Â Â Â Â Â Â Â Â Â Â Â Â int decreasing[], int m1, int m2) { Â
    // Initialize variable to     // find the minimum element     int mini = INT_MAX; Â
    // Find minimum element in     // increasing[] array     for(int i = 0; i < m1; i++)    {         if (mini > increasing[i])             mini = increasing[i];     } Â
    // Initialize variable to     // find the maximum element     int maxi = INT_MIN; Â
    // Find maximum element in     // decreasing[] array     for(int i = 0; i < m2; i++)    {         if (maxi < decreasing[i])             maxi = decreasing[i];     } Â
    // Find the minimum steps     int minSteps = max(maxi,                        N - mini); Â
    // Print the minimum steps     cout << minSteps << endl;} Â
// Driver codeint main() {Â Â Â Â Â Â Â Â Â // Given N Â Â Â Â int N = 7; Â
    // Given increasing     // and decreasing array     int increasing[] = { 3, 5 };     int decreasing[] = { 6 };          // Find length of arrays    // increasing and decreasing    int m1 = sizeof(increasing) /sizeof(increasing[0]);    int m2 = sizeof(decreasing) / sizeof(decreasing[0]);         // Function call     minSteps(N, increasing, decreasing, m1, m2); }Â
// This code is contributed by Manne Sree Charan |
Java
// Java program for the above approach import java.util.*; Â
public class GFG { Â
    // Function that finds the minimum     // steps to reach either 0 or N for     // given increasing and decreasing     // arrays     public static void    minSteps(int N, int[] increasing,             int[] decreasing)     { Â
        // Initialize variable to         // find the minimum element         int min = Integer.MAX_VALUE; Â
        // Find minimum element in         // increasing[] array         for (int i : increasing) {             if (min > i)                 min = i;         } Â
        // Initialize variable to         // find the maximum element         int max = Integer.MIN_VALUE; Â
        // Find maximum element in         // decreasing[] array         for (int i : decreasing) {             if (max < i)                 max = i;         } Â
        // Find the minimum steps         int minSteps = Math.max(max,                                 N - min); Â
        // Print the minimum steps         System.out.println(minSteps);     } Â
    // Driver Code     public static void main(String[] args)     {         // Given N         int N = 7; Â
        // Given increasing         // and decreasing array         int increasing[] = { 3, 5 };         int decreasing[] = { 6 }; Â
        // Function call         minSteps(N, increasing, decreasing);     } } |
Python3
# Python3 program for # the above approachimport sysÂ
# Function that finds the minimum# steps to reach either 0 or N for# given increasing and decreasing# arraysdef minSteps(N, increasing, decreasing):    # Initialize variable to    # find the minimum element    Min = sys.maxsize;Â
    # Find minimum element in    # increasing array    for i in increasing:        if (Min > i):            Min = i;Â
    # Initialize variable to    # find the maximum element    Max = -sys.maxsize;Â
    # Find maximum element in    # decreasing array    for i in decreasing:        if (Max < i):            Max = i;Â
    # Find the minimum steps    minSteps = max(Max, N - Min);Â
    # Print the minimum steps    print(minSteps);Â
# Driver Codeif __name__ == '__main__':Â Â Â Â Â Â Â # Given NÂ Â Â Â N = 7;Â
    # Given increasing    # and decreasing array    increasing = [3, 5];    decreasing = [6];Â
    # Function call    minSteps(N, increasing, decreasing);Â
# This code contributed by Rajput-Ji |
C#
// C# program for the above approach using System;Â
class GFG{ Â
// Function that finds the minimum // steps to reach either 0 or N for // given increasing and decreasing // arrays public static void minSteps(int N, int[] increasing, Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â int[] decreasing) { Â
    // Initialize variable to     // find the minimum element     int min = int.MaxValue; Â
    // Find minimum element in     // increasing[] array     foreach(int i in increasing)     {         if (min > i)             min = i;     } Â
    // Initialize variable to     // find the maximum element     int max = int.MinValue; Â
    // Find maximum element in     // decreasing[] array     foreach(int i in decreasing)     {         if (max < i)             max = i;     } Â
    // Find the minimum steps     int minSteps = Math.Max(max,                             N - min); Â
    // Print the minimum steps     Console.WriteLine(minSteps); } Â
// Driver Code public static void Main(String[] args) { Â Â Â Â Â Â Â Â Â // Given N Â Â Â Â int N = 7; Â
    // Given increasing     // and decreasing array     int []increasing = { 3, 5 };     int []decreasing = { 6 }; Â
    // Function call     minSteps(N, increasing, decreasing); } }Â
// This code is contributed by Amit Katiyar |
Javascript
<script>Â
// Javascript program for the above approachÂ
// Function that finds the minimum // steps to reach either 0 or N for // given increasing and decreasing // arrays function minSteps(N, increasing, decreasing, m1, m2) { Â
    // Initialize variable to     // find the minimum element     var mini = 2147483647;          var i;    // Find minimum element in     // increasing[] array     for(i = 0; i < m1; i++)    {         if (mini > increasing[i])             mini = increasing[i];     } Â
    // Initialize variable to     // find the maximum element     var maxi = -2147483648; Â
    // Find maximum element in     // decreasing[] array     for(i = 0; i < m2; i++)    {         if (maxi < decreasing[i])             maxi = decreasing[i];     } Â
    // Find the minimum steps     var minSteps = Math.max(maxi,N - mini); Â
    // Print the minimum steps     document.write(minSteps);} Â
// Driver code      // Given N     var N = 7; Â
    // Given increasing     // and decreasing array     var increasing = [3, 5];     var decreasing = [6];          // Find length of arrays    // increasing and decreasing    var m1 = increasing.length;    var m2 = decreasing.length;         // Function call     minSteps(N, increasing, decreasing, m1, m2); Â
// This code is contributed by bgangwar59.</script> |
Output:Â
6
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!
… [Trackback]
[…] Here you will find 22029 more Info on that Topic: geeksforgeeks.org/minimum-steps-for-increasing-and-decreasing-array-to-reach-either-0-or-n/ […]
… [Trackback]
[…] Find More here on that Topic: geeksforgeeks.org/minimum-steps-for-increasing-and-decreasing-array-to-reach-either-0-or-n/ […]