Minimize consecutive elements to be added for each element to make Array of at least C length
Given a sorted array arr[] of size N, where arr[i] denotes the starting position of a sequence, the task is to find the minimum number of consecutive elements (say K) that can be added for each Array element to make the Array length at least C.
Note: The consecutive numbers can be added till minimum of arr[i]+K or (arr[i+1]-1).
Examples:
Input: arr[] = { 1, 2, 4, 5, 7}, C = 3
Output: 1
Explanation: For K = 1, 5 numbers are possible(one from each position).
From position 1 – select ‘1’.
From position 2 – select ‘2’
From position 4 – select ‘4’
From position 5 – select ‘5’
From position 7 – select ‘7’
Total elements of sequence =5, which is greater than 3Input: arr [] = {2, 4, 10}, C = 10
Output: 4
Explanation: Given sequences are: {2, 3}, {4, 5, 6, 7, 8, 9}, {10, 11, 12, 13, 14 . . . }
Selected elements = { 2, 3, 4, 5, 6, 7, 10, 11, 12, 13}
Minimum value should be 4.
From position 2 -> 2, 3 because
the next sequence starts at 4 so 4 elements cannot be selected from this sequence
From position 4 – 4, 5, 6, 7
From position 10 – 10, 11, 12, 13
Total elements of sequence = 10 { 2, 3, 4, 5, 6, 7, 10, 11, 12, 13}.
Naive Approach: The basic idea to solve the problem is by simply traversing the array.
Follow the steps mentioned below:
- Start from taking K = 1, and for each K check if it is possible to get C elements of the sequences.
- If possible then K is the answer otherwise increment K by 1 and continue until the condition is satisfied.
Time Complexity: O(N*C)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved based on the following idea:
Use Binary Search on K. If for any value of K it is possible to find C elements in the sequence then try for a lower value in the lower half. Otherwise, try for a higher value of K in the higher half.
Follow the steps to solve the problem:
- Try to find the value of K in the range of 1 to C by using the binary search by setting low = 1 and high = C;
- If at least C elements got collected, then check on the left half to find the minimum value of K.
- If not, then check on the upper half (that is for values greater than mid value).
- After the search is complete return low which will represent minimum K.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach. #include <bits/stdc++.h> using namespace std; // Function to find the min value of K void solver(vector< int > arr, int C) { int low = 1; int high = C; int mid = 0; int sum = 0; int n = arr.size(); // Binary search to find min of K while (low < high) { mid = (low + high) / 2; sum = mid; for ( int k = 1; k < n; k++) { sum += min(mid, arr[k] - arr[k - 1]); } // If atleast C numbers are found, // then search in left side // to get minimum value of k if (sum >= C) { high = mid; } else { // If we are not able to get // atleast C elements, // then move in // right direction low = mid + 1; } } cout << low << endl; } // Driver code int main() { vector< int > arr = { 2, 4, 10 }; int C = 10; solver(arr, C); } // This code is contributed by Taranpreet |
Java
// Java code to implement the above approach. import java.io.*; class GFG { // Function to find the min value of K public static void solver( int [] arr, int C) { int low = 1 ; int high = C; int mid = 0 ; int sum = 0 ; int n = arr.length; // Binary search to find min of K while (low < high) { mid = (low + high) / 2 ; sum = mid; for ( int k = 1 ; k < n; k++) { sum += Math.min(mid, arr[k] - arr[k - 1 ]); } // If atleast C numbers are found, // then search in left side // to get minimum value of k if (sum >= C) { high = mid; } else { // If we are not able to get // atleast C elements, // then move in // right direction low = mid + 1 ; } } System.out.println(low); } // Driver code public static void main(String[] args) { int arr[] = { 2 , 4 , 10 }; int C = 10 ; solver(arr, C); } } |
Python3
# Python code for the above approach # Function to find the min value of K def solver(arr, C): low = 1 high = C mid = 0 sum = 0 n = len (arr) # Binary search to find min of K while (low < high): mid = (low + high) / / 2 sum = mid for k in range ( 1 ,n): sum + = min (mid,arr[k] - arr[k - 1 ]) # If atleast C numbers are found, # then search in left side # to get minimum value of k if ( sum > = C): high = mid else : # If we are not able to get # atleast C elements, # then move in # right direction low = mid + 1 print (low) # Driver code arr = [ 2 , 4 , 10 ] C = 10 solver(arr, C) # This code is contributed byshinjanpatra |
C#
// C# code to implement the above approach. using System; class GFG { // Function to find the min value of K static void solver( int [] arr, int C) { int low = 1; int high = C; int mid = 0; int sum = 0; int n = arr.Length; // Binary search to find min of K while (low < high) { mid = (low + high) / 2; sum = mid; for ( int k = 1; k < n; k++) { sum += Math.Min(mid, arr[k] - arr[k - 1]); } // If atleast C numbers are found, // then search in left side // to get minimum value of k if (sum >= C) { high = mid; } else { // If we are not able to get // atleast C elements, // then move in // right direction low = mid + 1; } } Console.WriteLine(low); } // Driver code public static void Main() { int []arr = { 2, 4, 10 }; int C = 10; solver(arr, C); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the min value of K function solver(arr, C) { let low = 1; let high = C; let mid = 0; let sum = 0; let n = arr.length; // Binary search to find min of K while (low < high) { mid = Math.floor((low + high) / 2); sum = mid; for (let k = 1; k < n; k++) { sum += Math.min(mid, arr[k] - arr[k - 1]); } // If atleast C numbers are found, // then search in left side // to get minimum value of k if (sum >= C) { high = mid; } else { // If we are not able to get // atleast C elements, // then move in // right direction low = mid + 1; } } document.write(low); } // Driver code let arr = [2, 4, 10]; let C = 10; solver(arr, C); // This code is contributed by Potta Lokesh </script> |
4
Time Complexity: O(N * log C)
Auxiliary Space: O(1)
Contact Us