Minimize value of a in series a, a/b^1, a/b^2, a/b^3, …, a/b^n such that sum of initial non-zero terms becomes at least S
Given two integers b and S. The task is to find the minimum value of ‘a‘ such that sum of becomes equal or greater than ‘S‘ for initial non-zero terms.
a, a/b1, a/b2, a/b3, …………., a/bn
Example:
Input: b = 2, S = 4
Output: 3
Explanation:
- Let a = 1, S = 1/20 + 1/21 = 1 + 0 = 1 < 4.
- Let a =2, S = 2/20 + 2/21 + 2/22 = 2 + 1 + 0 = 3 < 4.
- Let a = 3, S = 3/20 + 3/21 + 3/22 = 3 + 1 + 0 = 4 = S.
So, a = 3 is the answer.
Input: b = 8, S = 25
Output: 23
Approach: This problem can be solved using binary search to find the answer. Obviously, if the number ‘a‘ is an answer, then every number n > a is also an answer because the values would only become more but we need the find the minimum one. So, to check some number ‘a’ we can use the formula given in the problem itself. Follow the steps below to solve the problem:
- Initialize the variables a as 1, low as 0, and high as S.
- Traverse in a while loop till low is less than equal to high and perform the following tasks:
- Initialize the variable mid as the average of low and high.
- Initialize x as b and sum as mid.
- Traverse in a while loop till mid/x is greater than 0 and perform the following tasks:
- Add the value of mid/x to the variable sum.
- Multiply the value b to the variable x.
- If sum is greater than equal to S then set a as mid and high as mid-1.
- Else set low as mid+1.
- After performing the above steps, print the value of a as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum value // of numerator such that sum of certain // terms in the given series become // equal or greater than X int findMinNumerator( int b, int S) { // Variable to store the ans // initialized with 1 which // can be the minimum answer int a = 1; int low = 0, high = S; // Iterate till low is less or // equal to high while (low <= high) { // Find the mid value int mid = (low + high) / 2; int x = b, sum = mid; // While mid / x is greater than // 0 keep updating sum and x while (mid / x > 0) { sum += mid / x; x *= b; } // If sum is greater than S, // store mid in ans and update // high to search other minimum if (sum >= S) { a = mid; high = mid - 1; } // Else update low as (mid + 1) else if (sum < S) { low = mid + 1; } } // Return the answer return a; } // Driver Code int main() { int b = 2, S = 4; cout << findMinNumerator(b, S); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to find the minimum value // of numerator such that sum of certain // terms in the given series become // equal or greater than X static int findMinNumerator( int b, int S) { // Variable to store the ans // initialized with 1 which // can be the minimum answer int a = 1 ; int low = 0 , high = S; // Iterate till low is less or // equal to high while (low <= high) { // Find the mid value int mid = (low + high) / 2 ; int x = b, sum = mid; // While mid / x is greater than // 0 keep updating sum and x while (mid / x > 0 ) { sum += mid / x; x *= b; } // If sum is greater than S, // store mid in ans and update // high to search other minimum if (sum >= S) { a = mid; high = mid - 1 ; } // Else update low as (mid + 1) else if (sum < S) { low = mid + 1 ; } } // Return the answer return a; } // Driver Code public static void main(String args[]) { int b = 2 , S = 4 ; System.out.println(findMinNumerator(b, S)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python 3 program for the above approach # Function to find the minimum value # of numerator such that sum of certain # terms in the given series become # equal or greater than X def findMinNumerator(b, S): # Variable to store the ans # initialized with 1 which # can be the minimum answer a = 1 low = 0 high = S # Iterate till low is less or # equal to high while (low < = high): # Find the mid value mid = (low + high) / / 2 x = b sum = mid # While mid / x is greater than # 0 keep updating sum and x while (mid / / x > 0 ): sum + = mid / / x x * = b # If sum is greater than S, # store mid in ans and update # high to search other minimum if ( sum > = S): a = mid high = mid - 1 # Else update low as (mid + 1) elif ( sum < S): low = mid + 1 # Return the answer return a # Driver Code if __name__ = = "__main__" : b = 2 S = 4 print (findMinNumerator(b, S)) # This code is contributed by ukasp. |
C#
// C# program for the above approach using System; using System.Collections; public class GFG { // Function to find the minimum value // of numerator such that sum of certain // terms in the given series become // equal or greater than X static int findMinNumerator( int b, int S) { // Variable to store the ans // initialized with 1 which // can be the minimum answer int a = 1; int low = 0, high = S; // Iterate till low is less or // equal to high while (low <= high) { // Find the mid value int mid = (low + high) / 2; int x = b, sum = mid; // While mid / x is greater than // 0 keep updating sum and x while (mid / x > 0) { sum += mid / x; x *= b; } // If sum is greater than S, // store mid in ans and update // high to search other minimum if (sum >= S) { a = mid; high = mid - 1; } // Else update low as (mid + 1) else if (sum < S) { low = mid + 1; } } // Return the answer return a; } // Driver Code public static void Main() { int b = 2, S = 4; Console.Write(findMinNumerator(b, S)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum value // of numerator such that sum of certain // terms in the given series become // equal or greater than X function findMinNumerator(b, S) { // Variable to store the ans // initialized with 1 which // can be the minimum answer let a = 1; let low = 0, high = S; // Iterate till low is less or // equal to high while (low <= high) { // Find the mid value let mid = Math.floor((low + high) / 2); let x = b, sum = mid; // While mid / x is greater than // 0 keep updating sum and x while (Math.floor(mid / x) > 0) { sum += mid / x; x *= b; } // If sum is greater than S, // store mid in ans and update // high to search other minimum if (sum >= S) { a = mid; high = mid - 1; } // Else update low as (mid + 1) else if (sum < S) { low = mid + 1; } } // Return the answer return a; } // Driver Code let b = 2, S = 4; document.write(findMinNumerator(b, S)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(log2N)
Auxiliary Space: O(1)
Contact Us