Dados dos enteros b y S . La tarea es encontrar el valor mínimo de ‘ a ‘ tal que la suma de sea igual o mayor que ‘ S ‘ para los términos iniciales distintos de cero.
a, a/b 1 , a/b 2 , a/b 3 , …………., a/b n
Ejemplo:
Entrada: b = 2, S = 4
Salida: 3
Explicación:
- Sea a = 1, S = 1/2 0 + 1/2 1 = 1 + 0 = 1 < 4.
- Sea a =2, S = 2/2 0 + 2/2 1 + 2/2 2 = 2 + 1 + 0 = 3 < 4.
- Sea a = 3, S = 3/2 0 + 3/2 1 + 3/2 2 = 3 + 1 + 0 = 4 = S.
Entonces, a = 3 es la respuesta.
Entrada: b = 8, S = 25
Salida: 23
Enfoque: este problema se puede resolver mediante la búsqueda binaria para encontrar la respuesta. Obviamente, si el número ‘ a ‘ es una respuesta, entonces cada número n > a también es una respuesta porque los valores solo se volverían más pero necesitamos encontrar el mínimo . Entonces, para verificar algún número ‘a’ podemos usar la fórmula dada en el problema mismo. Siga los pasos a continuación para resolver el problema:
- Inicialice las variables a como 1, bajo como 0 y alto como S.
- Atraviese un bucle while hasta que el nivel bajo sea menor que el alto y realice las siguientes tareas:
- Inicialice la variable mid como el promedio de low y high.
- Inicializa x como b y suma como mid.
- Atraviese un bucle while hasta que mid/x sea mayor que 0 y realice las siguientes tareas:
- Agregue el valor de mid/x a la variable sum .
- Multiplica el valor b por la variable x.
- Si la suma es mayor que igual a S , establezca a como medio y alto como medio-1.
- De lo contrario, ajuste bajo como mid+1.
- Después de realizar los pasos anteriores, imprima el valor de a como respuesta.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
3
Complejidad de tiempo: O(log 2 N)
Espacio auxiliar: O(1)