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 conditionint 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 codeint 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 approachimport java.io.*; import java.lang.Math;class GFG {// Function to return the minimum value of k// that satisfies the given conditionstatic 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 codepublic 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 = 200print(findMinimumK(a, n, s))# This code is contributed by Sanjit_Prasad |
C#
// C# implementation of the approachusing System;class GFG {// Function to return the minimum value of k// that satisfies the given conditionstatic 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 codepublic 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)
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!
