Dado un entero k y una secuencia monótona creciente:
f(n) = an + bn [log2(n)] + cn^3 donde ( a = 1, 2, 3, …), ( b = 1, 2, 3, …), ( c = 0, 1, 2, 3, …)
Aquí, [log 2 (n)] significa llevar el logaritmo a la base 2 y redondear el valor hacia abajo. Por lo tanto,
si n = 1, el valor es 0
Si n = 2-3, el valor es 1. Si
n = 4-7, el valor es 2.
Si n = 8-15, el valor es 3.
La tarea es encontrar el valor n tal que f(n ) = k , si k no pertenece a la secuencia, imprima 0 .
Nota: Los valores están de tal forma que se pueden expresar en 64 bits y los tres enteros a, b y c no superan 100.
Ejemplos:
Entrada: a = 2, b = 1, c = 1, k = 12168587437017
Salida: 23001
f(23001) = 12168587437017Entrada: a = 7, b = 3, c = 0, k = 119753085330
Salida: 1234567890
Enfoque ingenuo: valores dados de a, b, c, encontrar valores de f(n) para cada valor de n y compararlos.
Enfoque eficiente: utilice la búsqueda binaria, elija n = (mín. + máx.) / 2, donde mín . y máx . son los valores mínimo y máximo posibles para n , luego,
- Si f(n) < k entonces incrementa n .
- Si f(n) > k entonces decrementa n .
- Si f(n) = k entonces n es la respuesta requerida.
- Repita los pasos anteriores hasta que se encuentre el valor requerido o no sea posible en la secuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
#include <math.h>
#define SMALL_N 1000000
#define LARGE_N 1000000000000000
using namespace std;
// Function to return the value of f(n) for given values of a, b, c, n
long long func(long long a, long long b, long long c, long long n)
{
long long res = a * n;
long long logVlaue = floor(log2(n));
res += b * n * logVlaue;
res += c * (n * n * n);
return res;
}
long long getPositionInSeries(long long a, long long b,
long long c, long long k)
{
long long start = 1, end = SMALL_N;
// if c is 0, then value of n can be in order of 10^15.
// if c!=0, then n^3 value has to be in order of 10^18
// so maximum value of n can be 10^6.
if (c == 0) {
end = LARGE_N;
}
long long ans = 0;
// for efficient searching, use binary search.
while (start <= end) {
long long mid = (start + end) / 2;
long long val = func(a, b, c, mid);
if (val == k) {
ans = mid;
break;
}
else if (val > k) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return ans;
}
// Driver code
int main()
{
long long a = 2, b = 1, c = 1;
long long k = 12168587437017;
cout << getPositionInSeries(a, b, c, k);
return 0;
}
Python3
# Python 3 implementation of the approach from math import log2, floor SMALL_N = 1000000 LARGE_N = 1000000000000000 # Function to return the value of f(n) # for given values of a, b, c, n def func(a, b, c, n) : res = a * n logVlaue = floor(log2(n)) res += b * n * logVlaue res += c * (n * n * n) return res def getPositionInSeries(a, b, c, k) : start = 1 end = SMALL_N # if c is 0, then value of n # can be in order of 10^15. # if c!=0, then n^3 value has # to be in order of 10^18 # so maximum value of n can be 10^6. if (c == 0) : end = LARGE_N ans = 0 # for efficient searching, # use binary search. while (start <= end) : mid = (start + end) // 2 val = func(a, b, c, mid) if (val == k) : ans = mid break elif (val > k) : end = mid - 1 else : start = mid + 1 return ans; # Driver code if __name__ == "__main__" : a = 2 b = 1 c = 1 k = 12168587437017 print(getPositionInSeries(a, b, c, k)) # This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// from math import log2, floor
$SMALL_N = 1000000;
$LARGE_N = 1000000000000000;
// Function to return the value of f(n)
// for given values of a, b, c, n
function func($a, $b, $c, $n)
{
$res = $a * $n;
$logVlaue = floor(log($n, 2));
$res += $b * $n * $logVlaue;
$res += $c * ($n * $n * $n);
return $res;
}
function getPositionInSeries($a, $b, $c, $k)
{
global $SMALL_N, $LARGE_N;
$start = 1;
$end = $SMALL_N;
// if c is 0, then value of n
// can be in order of 10^15.
// if c!=0, then n^3 value has
// to be in order of 10^18
// so maximum value of n can be 10^6.
if ($c == 0)
$end = $LARGE_N;
$ans = 0;
// for efficient searching,
// use binary search.
while ($start <= $end)
{
$mid = (int)(($start + $end) / 2);
$val = func($a, $b, $c, $mid) ;
if ($val == $k)
{
$ans = $mid;
break;
}
else if ($val > $k)
$end = $mid - 1;
else
$start = $mid + 1;
}
return $ans;
}
// Driver code
$a = 2;
$b = 1;
$c = 1;
$k = 12168587437017;
print(getPositionInSeries($a, $b, $c, $k));
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
const SMALL_N = 1000000;
const LARGE_N = 1000000000000000;
// Function to return the value of f(n)
// for given values of a, b, c, n
function func(a, b, c, n)
{
let res = a * n;
let logVlaue = Math.floor(Math.log(n) /
Math.log(2));
res += b * n * logVlaue;
res += c * (n * n * n);
return res;
}
function getPositionInSeries(a, b, c, k)
{
let start = 1, end = SMALL_N;
// If c is 0, then value of n can be
// in order of 10^15. If c!=0, then
// n^3 value has to be in order of 10^18
// so maximum value of n can be 10^6.
if (c == 0)
{
end = LARGE_N;
}
let ans = 0;
// For efficient searching, use binary search.
while (start <= end)
{
let mid = parseInt((start + end) / 2);
let val = func(a, b, c, mid);
if (val == k)
{
ans = mid;
break;
}
else if (val > k)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
}
return ans;
}
// Driver code
let a = 2, b = 1, c = 1;
let k = 12168587437017;
document.write(getPositionInSeries(a, b, c, k));
// This code is contributed by souravmahato348
</script>
23001
Complejidad Temporal: O(log n), ya que es una búsqueda binaria donde cada vez los elementos se reducen a la mitad.
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.