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!
