Given an array A of n integers and two integers p and q, the task is to increase some (or all) of the values in array A in such a way that ratio of each element (after first element) with respect to the total sum of all elements before the current element remains less than or equal to p/q. Return the minimum sum of changes to be done.
Examples:
Input: n = 4, A = {20100, 1, 202, 202}, p = 1, q = 100
Output: 99
Explanation: 50 is added to the first element and 49 to the second element, so that the resulting array becomes {20150, 50, 202, 202}.
50/20150 <= 1/100
202/(20150+50) <=1/100
202/(20150+50+202)<=1/100
Therefore, the condition is satisfied for all the elements and hence 50+49=99 would be the answer.
There are other answers possible as well, but we need to find out the minimum possible sum.Input: n = 3, A = {1, 1, 1}, p = 100, q = 100
Output: 0
Approach: The problem can be easily solved using the concepts of prefix sum and binary search.
- It can be clearly observed that
- if the condition stated in the problem is achieved for a certain sum of changes (say S),
- then it is always possible to achieve the condition for all the numbers greater than S and
- cannot be achieved for all numbers less than S.
- So, we can apply binary search to find the answer.
- Also, it must be carefully observed that instead of distributing S(sum of changes) over different elements, if we just add it to first element, that would not affect the answer.
For example, in the first example above, if 99 is added to the first element, the resultant array will still meet the required condition.
Follow the steps below to solve the problem –
- Make a prefix sum array of the given array.
- Using binary search on range 0 to INT_MAX find the minimum possible answer.
NOTE: Division may lead to overlapping values and errors.
So, instead of comparison like (a/b)<=(c/d), we will do (a*d)<=(b*c).
Below is the implementation of the above approach:
C++
// C++ program for find minimum// sum of changes in an array#include <bits/stdc++.h>using namespace std;// function to check if the candidate sum// satisfies the condition of the problembool isValid(int candidate, int pre[], int n, int A[], int p, int q){ // flag variable to check wrong answer bool flag = true; for (int i = 1; i < n; i++) { // Now for each element, we are checking // if its ratio with sum of all previous // elements + candidate is greater than p/q. // If so, we will return false. int curr_sum = pre[i - 1] + candidate; if (A[i] * q > p * curr_sum) { flag = false; break; } // comparing like A[i]/(curr_sum)>p/q // will be error prone. } return flag;}int solve(int n, int A[], int p, int q){ // declaring and constructing // prefix sum array int pre[n]; pre[0] = A[0]; for (int i = 1; i < n; i++) { pre[i] = A[i] + pre[i - 1]; } // setting lower and upper bound for // binary search int lo = 0, hi = INT_MAX, ans = INT_MAX; // since minimum answer is needed, // so it is initialized with INT_MAX while (lo <= hi) { // calculating mid by using (lo+hi)/2 // may overflow in certain cases int mid = lo + (hi - lo) / 2; // checking if required ratio would be // achieved by all elements if "mid" is // considered as answer if (isValid(mid, pre, n, A, p, q)) { ans = mid; hi = mid - 1; } else { lo = mid + 1; } } return ans;}// Driver Functionint main(){ int n, p, q; n = 4, p = 1, q = 100; int A[] = { 20100, 1, 202, 202 }; // printing the required answer cout << solve(n, A, p, q) << endl;} |
Java
// Java program for find minimum// sum of changes in an arraykage whatever //do not write package name here */import java.io.*;class GFG { // function to check if the candidate sum // satisfies the condition of the problem static Boolean isValid(int candidate, int pre[], int n, int A[], int p, int q) { // flag variable to check wrong answer Boolean flag = true; for (int i = 1; i < n; i++) { // Now for each element, we are checking // if its ratio with sum of all previous // elements + candidate is greater than p/q. // If so, we will return false. int curr_sum = pre[i - 1] + candidate; if (A[i] * q > p * curr_sum) { flag = false; break; } // comparing like A[i]/(curr_sum)>p/q // will be error prone. } return flag; } static int solve(int n, int A[], int p, int q) { // declaring and constructing // prefix sum array int pre[] = new int[n]; pre[0] = A[0]; for (int i = 1; i < n; i++) { pre[i] = A[i] + pre[i - 1]; } // setting lower and upper bound for // binary search int lo = 0, hi = Integer.MAX_VALUE, ans = Integer.MAX_VALUE; // since minimum answer is needed, // so it is initialized with INT_MAX while (lo <= hi) { // calculating mid by using (lo+hi)/2 // may overflow in certain cases int mid = lo + (hi - lo) / 2; // checking if required ratio would be // achieved by all elements if "mid" is // considered as answer if (isValid(mid, pre, n, A, p, q)) { ans = mid; hi = mid - 1; } else { lo = mid + 1; } } return ans; } // Driver Function public static void main (String[] args) { int n = 4, p = 1, q = 100; int A[] = { 20100, 1, 202, 202 }; // printing the required answer System.out.println(solve(n, A, p, q)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approachimport sys# function to check if the candidate sum# satisfies the condition of the problemdef isValid(candidate, pre, n, A, p, q) : # flag variable to check wrong answer flag = True for i in range(1, n) : # Now for each element, we are checking # if its ratio with sum of all previous # elements + candidate is greater than p/q. # If so, we will return false. curr_sum = pre[i - 1] + candidate if (A[i] * q > p * curr_sum) : flag = False break # comparing like A[i]/(curr_sum)>p/q # will be error prone. return flag def solve(n, A, p, q) : # declaring and constructing # prefix sum array pre = [0] * 100 pre[0] = A[0] for i in range(1, n) : pre[i] = A[i] + pre[i - 1] # setting lower and upper bound for # binary search lo = 0 hi = sys.maxsize ans = sys.maxsize # since minimum answer is needed, # so it is initialized with INT_MAX while (lo <= hi) : # calculating mid by using (lo+hi)/2 # may overflow in certain cases mid = lo + (hi - lo) // 2 # checking if required ratio would be # achieved by all elements if "mid" is # considered as answer if (isValid(mid, pre, n, A, p, q)) : ans = mid hi = mid - 1 else : lo = mid + 1 return ans # Driver Functionn = 4p = 1q = 100A = [ 20100, 1, 202, 202 ] # printing the required answerprint(solve(n, A, p, q))# This code is contributed by code_hunt. |
C#
// C# program for find minimum// sum of changes in an arrayusing System;class GFG{ // function to check if the candidate sum // satisfies the condition of the problem static bool isValid(int candidate, int []pre, int n, int []A, int p, int q) { // flag variable to check wrong answer bool flag = true; for (int i = 1; i < n; i++) { // Now for each element, we are checking // if its ratio with sum of all previous // elements + candidate is greater than p/q. // If so, we will return false. int curr_sum = pre[i - 1] + candidate; if (A[i] * q > p * curr_sum) { flag = false; break; } // comparing like A[i]/(curr_sum)>p/q // will be error prone. } return flag; } static int solve(int n, int []A, int p, int q) { // declaring and constructing // prefix sum array int []pre = new int[n]; pre[0] = A[0]; for (int i = 1; i < n; i++) { pre[i] = A[i] + pre[i - 1]; } // setting lower and upper bound for // binary search int lo = 0, hi = Int32.MaxValue, ans = Int32.MaxValue; // since minimum answer is needed, // so it is initialized with INT_MAX while (lo <= hi) { // calculating mid by using (lo+hi)/2 // may overflow in certain cases int mid = lo + (hi - lo) / 2; // checking if required ratio would be // achieved by all elements if "mid" is // considered as answer if (isValid(mid, pre, n, A, p, q)) { ans = mid; hi = mid - 1; } else { lo = mid + 1; } } return ans; } // Driver Function public static void Main() { int n = 4, p = 1, q = 100; int []A = { 20100, 1, 202, 202 }; // printing the required answer Console.WriteLine(solve(n, A, p, q)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for find minimum // sum of changes in an array const INT_MAX = 2147483647; // function to check if the candidate sum // satisfies the condition of the problem const isValid = (candidate, pre, n, A, p, q) => { // flag variable to check wrong answer let flag = true; for (let i = 1; i < n; i++) { // Now for each element, we are checking // if its ratio with sum of all previous // elements + candidate is greater than p/q. // If so, we will return false. let curr_sum = pre[i - 1] + candidate; if (A[i] * q > p * curr_sum) { flag = false; break; } // comparing like A[i]/(curr_sum)>p/q // will be error prone. } return flag; } let solve = (n, A, p, q) => { // declaring and constructing // prefix sum array let pre = new Array(n).fill(0); pre[0] = A[0]; for (let i = 1; i < n; i++) { pre[i] = A[i] + pre[i - 1]; } // setting lower and upper bound for // binary search let lo = 0, hi = INT_MAX, ans = INT_MAX; // since minimum answer is needed, // so it is initialized with INT_MAX while (lo <= hi) { // calculating mid by using (lo+hi)/2 // may overflow in certain cases let mid = lo + parseInt((hi - lo) / 2); // checking if required ratio would be // achieved by all elements if "mid" is // considered as answer if (isValid(mid, pre, n, A, p, q)) { ans = mid; hi = mid - 1; } else { lo = mid + 1; } } return ans; } // Driver Function let n, p, q; n = 4, p = 1, q = 100; let A = [20100, 1, 202, 202]; // printing the required answer document.write(solve(n, A, p, q));// This code is contributed by rakeshsahni</script> |
Output
99
Time Complexity: O(n log(INT_MAX))
Auxiliary space: O(n)
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!
Share your thoughts in the comments
