Encuentre el término n de la serie 1 2 2 4 4 4 4 8 8 8 8 8 8 8 8 …

Posted on by Rudeus Greyrat

Dado un número n, la tarea es encontrar el n-ésimo término de la Serie 
 

1 2 2 4 4 4 4 8 8 8 8 8 8 8 8 …

Ejemplo: 
 

Input: n = 9
Output: 8

Input: n = 1025
Output: 1024

Enfoque ingenuo: 
 

  1. Ejecutar un bucle de i = 0 a n
  2. Incremento de bucle interior i por i+k
  3. Incremento de bucle interior k en 2*k
  4. Ejecutar el ciclo anterior mientras i es menor que n
  5. Devuelve k/2 como resultado

Complejidad: log(n)
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// CPP Program to find Nth term
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that will return nth term
int getValue(int n)
{
    int i = 0, k = 1;
 
    while (i < n) {
        i = i + k;
        k = k * 2;
    }
 
    return k / 2;
}
 
// Driver Code
int main(void)
{
 
    // Get n
    int n = 9;
 
    // Get the value
    cout << getValue(n) << endl;
 
    // Get n
    n = 1025;
 
    // Get the value
    cout << getValue(n) << endl;
}

Java

// Java Program to find Nth term
 
class GFG
{
     
    // Function that will return nth term
    static int getValue(int n)
    {
        int i = 0, k = 1;
     
        while (i < n) {
            i = i + k;
            k = k * 2;
        }
     
        return k / 2;
    }
     
    // Driver Code
    public static void main(String []args)
    {
     
        // Get n
        int n = 9;
     
        // Get the value
        System.out.println(getValue(n));
         
        // Get n
        n = 1025;
     
        // Get the value
        System.out.println(getValue(n));
    }
}

Python3

# Python3 Program to find Nth term
 
# Function that will return nth term
def getValue(n):
 
    i = 0;
    k = 1;
 
    while (i < n):
        i = i + k;
        k = k * 2;
 
    return int(k / 2);
 
# Driver Code
 
# Get n
n = 9;
 
# Get the value
print(getValue(n));
 
# Get n
n = 1025;
 
# Get the value
print(getValue(n));
 
# This code is contributed by mits

C#

// C# Program to find Nth term
 
using System;
class GFG
{
     
    // Function that will return nth term
    static int getValue(int n)
    {
        int i = 0, k = 1;
     
        while (i < n) {
            i = i + k;
            k = k * 2;
        }
     
        return k / 2;
    }
     
    // Driver Code
    public static void Main()
    {
     
        // Get n
        int n = 9;
     
        // Get the value
        Console.WriteLine(getValue(n));
         
        // Get n
        n = 1025;
     
        // Get the value
        Console.WriteLine(getValue(n));
    }
}

PHP

<?php
// PHP Program to find Nth term
 
// Function that will return nth term
function getValue($n)
{
    $i = 0; $k = 1;
 
    while ($i < $n)
    {
        $i = $i + $k;
        $k = $k * 2;
    }
 
    return (int)$k / 2;
}
 
// Driver Code
 
// Get n
$n = 9;
 
// Get the value
echo getValue($n),"\n";
 
// Get n
$n = 1025;
 
// Get the value
echo getValue($n),"\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
// Javascript Program to find Nth term
 
// Function that will return nth term
function getValue(n)
{
    let i = 0, k = 1;
 
    while (i < n) {
        i = i + k;
        k = k * 2;
    }
 
    return parseInt(k / 2);
}
 
// Driver Code
 
    // Get n
    let n = 9;
 
    // Get the value
    document.write(getValue(n) + "<br>");
 
    // Get n
    n = 1025;
 
    // Get the value
    document.write(getValue(n) + "<br>");
 
// This code is contributed by subhammahato348.
</script>
Producción: 

8
1024

 

Enfoque eficiente: este problema se puede resolver en una complejidad de tiempo O (1). 
Sea el término n -ésimo de la secuencia igual a 2 m
1+2+4+8+.... +2^{m-1} < n \\ 2^m -1 <n \\ 2^m < n+1 \\ m < log_2 (n+1)\\
A continuación se muestra la implementación del enfoque anterior:
 

C++

// CPP Program to find Nth term
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that will return nth term
int getValue(int n)
{
    // Find log of n+1 on base 2
    int result = (floor)(log(n + 1) / log(2));
 
    return pow(2, result);
}
 
// Driver Code
int main(void)
{
    // Get n
    int n = 9;
 
    // Get the value
    cout << getValue(n) << endl;
 
    // Get n
    n = 1025;
 
    // Get the value
    cout << getValue(n) << endl;
}

Java

// Java Program to find Nth term
 
import java.lang.*;
import java.lang.Math;
import java.io.*;
 
class GFG {
    // Function that will return nth term
static double getValue(double n)
{
    // Find log of n+1 on base 2
 double result =(Math.floor(Math.log(n + 1) / Math.log(2)));
 
    return Math.pow(2, result);
}
 
// Driver Code
    public static void main (String[] args) {
    // Get n
    double n = 9;
    // Get the value
    System.out.println (getValue(n));
    // Get n
    n = 1025;
    // Get the value
        System.out.println (getValue(n));
    }
}

Python3

# Python3 Program to find Nth term
import math
 
# Function that will return nth term
def getValue(n):
 
    # Find log of n+1 on base 2
    result = int(math.floor(math.log(n + 1) /
                            math.log(2)))
    return int(math.pow(2, result))
 
# Driver code
n = 9
print(getValue(n))
 
n = 1025
print(getValue(n))
 
# This code is contributed
# by Shrikant13

C#

// C# Program to find Nth term
using System;
 
class GFG
{
    // Function that will return nth term
    static double getValue(double n)
    {
        // Find log of n+1 on base 2
        double result =(Math.Floor(Math.Log(n + 1) / Math.Log(2)));
        return Math.Pow(2, result);
    }
 
    // Driver Code
    public static void Main ()
    {
        // Get n
        double n = 9;
         
        // Get the value
        Console.WriteLine(getValue(n));
         
        // Get n
        n = 1025;
         
        // Get the value
        Console.WriteLine (getValue(n));
    }
}
 
// This code is contributed by SoM15242

PHP

<?php
// PHP Program to find Nth term
// Function that will return nth term
function getValue($n)
{
    // Find log of n+1 on base 2
    $result = (int)(log($n + 1) / log(2));
 
    return pow(2, $result);
}
 
// Driver Code
 
// Get n
$n = 9;
 
// Get the value
echo getValue($n), "\n";
 
// Get n
$n = 1025;
 
// Get the value
echo getValue($n), "\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
 // Javascript Program to find Nth term
 
// Function that will return nth term
function getValue(n)
{
    // Find log of n+1 on base 2
    let result = Math.floor(Math.log(n + 1) / Math.log(2));
 
    return Math.pow(2, result);
}
 
// Driver Code
// Get n
let n = 9;
 
// Get the value
document.write(getValue(n) + "<br>");
 
// Get n
n = 1025;
 
// Get the value
document.write(getValue(n));
 
// This code is contributed by subhammahato348.
</script>
Producción: 

8
1024

 

Complejidad de tiempo : O (logn) para el número dado n

Publicación traducida automáticamente

Artículo escrito por ankit15697 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *