Find minimum number K such that sum of array after multiplication by K exceed S
Given an array arr[] of N elements and an integer S, the task is to find the minimum number K such that the sum of the array elements does not exceed S after multiplying all the elements by K.
Examples:
Input: arr[] = { 1 }, S = 50
Output: 51
Explanation:
The sum of array elements is 1.
Now the multiplication of 1 with 51 gives 51 which is > 50.
Hence the minimum value of K is 51.
Input: arr[] = { 10, 7, 8, 10, 12, 19 }, S = 200
Output: 4
Explanation:
The sum of array elements is 66.
Now the multiplication of 66 with 4 gives 256 > 200.
Hence the minimum value of K is 4.
Approach:
- Find the sum of all elements of the array, store it in a variable sum.
- Take the ceil division of (S + 1) with sum. This will be the required minimum value of K.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum value of k // that satisfies the given condition int findMinimumK( int a[], int n, int S) { // store sum of array elements int sum = 0; // Calculate the sum after for ( int i = 0; i < n; i++) { sum += a[i]; } // return minimum possible K return ceil (((S + 1) * 1.0) / (sum * 1.0)); } // Driver code int main() { int a[] = { 10, 7, 8, 10, 12, 19 }; int n = sizeof (a) / sizeof (a[0]); int S = 200; cout << findMinimumK(a, n, S); return 0; } |
Java
// Java implementation of the approach import java.io.*; import java.lang.Math; class GFG { // Function to return the minimum value of k // that satisfies the given condition static int findMinimumK( int a[], int n, int S) { // Store sum of array elements int sum = 0 ; // Calculate the sum after for ( int i = 0 ; i < n; i++) { sum += a[i]; } // Return minimum possible K return ( int ) Math.ceil(((S + 1 ) * 1.0 ) / (sum * 1.0 )); } // Driver code public static void main(String[] args) { int a[] = { 10 , 7 , 8 , 10 , 12 , 19 }; int n = a.length; int S = 200 ; System.out.print(findMinimumK(a, n, S)); } } // This code is contributed by shivanisinghss2110 |
Python3
# Python3 implementation of the approach import math # Function to return the minimum value of k # that satisfies the given condition def findMinimumK(a, n, S) : # store sum of array elements sum = 0 # Calculate the sum after for i in range ( 0 ,n): sum + = a[i] # return minimum possible K return math.ceil(((S + 1 ) * 1.0 ) / ( sum * 1.0 )) # Driver code a = [ 10 , 7 , 8 , 10 , 12 , 19 ] n = len (a) s = 200 print (findMinimumK(a, n, s)) # This code is contributed by Sanjit_Prasad |
C#
// C# implementation of the approach using System; class GFG { // Function to return the minimum value of k // that satisfies the given condition static int findMinimumK( int []a, int n, int S) { // Store sum of array elements int sum = 0; // Calculate the sum after for ( int i = 0; i < n; i++) { sum += a[i]; } // Return minimum possible K return ( int ) Math.Ceiling(((S + 1) * 1.0) / (sum * 1.0)); } // Driver code public static void Main(String[] args) { int []a = { 10, 7, 8, 10, 12, 19 }; int n = a.Length; int S = 200; Console.Write(findMinimumK(a, n, S)); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript implementation of the approach // Function to return the minimum value of k // that satisfies the given condition function findMinimumK(a, n, S) { // store sum of array elements let sum = 0; // Calculate the sum after for (let i = 0; i < n; i++) { sum += a[i]; } // return minimum possible K return Math.ceil(((S + 1) * 1.0) / (sum * 1.0)); } let a = [ 10, 7, 8, 10, 12, 19 ]; let n = a.length; let S = 200; document.write(findMinimumK(a, n, S)); </script> |
Output:
4
Time Complexity: O(N)
Space Complexity: O(1)
Contact Us