Given an integer array H which represents heights of buildings and an integer K. The task is to reach the last building from the first with the following rules:
- Getting to a building of height Hj from a building of height Hi is only possible if |Hi – Hj| <= K and the building appears one after another in the array.
- If getting to a building is not possible then a number of buildings of intermediate heights can be inserted in between the two buildings.
Find the minimum number of insertions done in step 2 to make it possible to go from the first building to the last.
Examples:
Input: H[] = {2, 4, 8, 16}, K = 3
Output: 3
Add 1 building of height 5 between buildings of height 4 and 8.
And add 2 buildings of heights 11 and 14 respectively between buildings of height 8 and 16.
Input: H[] = {5, 55, 100, 1000}, K = 10
Output: 97
Approach:
- Run a loop from 1 to n-1 and check whether abs(H[i] – H[i-1]) <= K.
- If the above condition is true then skip to the next iteration of the loop.
- If the condition is false, then the insertions required will be equal to ceil(diff / K) – 1 where diff = abs(H[i] – H[i-1])
- Print the total insertions in the end.
Below is the implementation of the above approach:
C++
// CPP implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to return minimum// number of insertions requiredint minInsertions(int H[], int n, int K){ // Initialize insertions to 0 int insert = 0; for (int i = 1; i < n; ++i) { float diff = abs(H[i] - H[i - 1]); if (diff <= K) continue; else insert += ceil(diff / K) - 1; } // return total insertions return insert;}// Driver programint main(){ int H[] = { 2, 4, 8, 16 }, K = 3; int n = sizeof(H) / sizeof(H[0]); cout << minInsertions(H, n, K); return 0;} |
Java
// Java implementation of above approachclass GFG{// Function to return minimum// number of insertions requiredstatic int minInsertions(int[] H, int n, int K){ // Initialize insertions to 0 int insert = 0; for (int i = 1; i < n; ++i) { float diff = Math.abs(H[i] - H[i - 1]); if (diff <= K) continue; else insert += Math.ceil(diff / K) - 1; } // return total insertions return insert;}// Driver programpublic static void main(String[] args){ int[] H = new int[]{ 2, 4, 8, 16 }; int K = 3; int n = H.length; System.out.println(minInsertions(H, n, K));}}// This code is contributed by mits |
Python3
# Python3 implementation of above approachimport math# Function to return minimum# number of insertions requireddef minInsertions(H, n, K): # Initialize insertions to 0 insert = 0; for i in range(1, n): diff = abs(H[i] - H[i - 1]); if (diff <= K): continue; else: insert += math.ceil(diff / K) - 1; # return total insertions return insert;# Driver CodeH = [2, 4, 8, 16 ];K = 3;n = len(H);print(minInsertions(H, n, K));# This code is contributed # by mits |
C#
// C# implementation of above approachusing System;class GFG{// Function to return minimum// number of insertions requiredstatic int minInsertions(int[] H, int n, int K){ // Initialize insertions to 0 int insert = 0; for (int i = 1; i < n; ++i) { float diff = Math.Abs(H[i] - H[i - 1]); if (diff <= K) continue; else insert += (int)Math.Ceiling(diff / K) - 1; } // return total insertions return insert;}// Driver Codestatic void Main(){ int[] H = new int[]{ 2, 4, 8, 16 }; int K = 3; int n = H.Length; Console.WriteLine(minInsertions(H, n, K));}}// This code is contributed by mits |
PHP
<?php// PHP implementation of above approach// Function to return minimum// number of insertions requiredfunction minInsertions($H, $n, $K){ // Initialize insertions to 0 $insert = 0; for ($i = 1; $i < $n; ++$i) { $diff = abs($H[$i] - $H[$i - 1]); if ($diff <= $K) continue; else $insert += ceil($diff / $K) - 1; } // return total insertions return $insert;}// Driver Code$H = array(2, 4, 8, 16 );$K = 3;$n = sizeof($H);echo minInsertions($H, $n, $K);// This code is contributed // by Akanksha Rai(Abby_akku)?> |
Javascript
<script>// Javascript implementation of above approach// Function to return minimum// number of insertions requiredfunction minInsertions( H, n, K){ // Initialize insertions to 0 var insert = 0; for (var i = 1; i < n; ++i) { var diff = Math.abs(H[i] - H[i - 1]); if (diff <= K) continue; else insert += Math.ceil(diff / K) - 1; } // return total insertions return insert;}var H = [ 2, 4, 8, 16 ];var K = 3;var n = H.length;document.write(minInsertions(H, n, K));// This code is contributed by SoumikMondal</script> |
Output
3
Complexity Analysis:
- Time Complexity: O(N), since a loop runs for N times.
- Auxiliary Space: O(1), since no extra space has been taken.
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!
