Find nth Term of the Series 1 2 2 4 4 4 4 8 8 8 8 8 8 8 8 …

0 0 5 minutes read

Given a number n, the task is to find the nth term of the Series

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

Example:

Input: n = 9
Output: 8

Input: n = 1025
Output: 1024

Naive Approach:

Run a loop from i = 0 to n
Inside loop increment i by i+k
Inside loop increment k by 2*k
Run above loop while i is less than n
Return k/2 as the result

Complexity: log(n)
Below is the implementation of the above approach:

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>

Output:

8
1024

Time Complexity: O(n / k)

Auxiliary Space: O(1)

Efficient Approach: This Problem can be solved in O(1) time complexity.
Let n^th term of the sequence be equal to 2^m
$1+2+4+8+.... +2^{m-1} < n \\ 2^m -1 <n \\ 2^m < n+1 \\ m < log_2 (n+1)\\$
Below is the implementation of the above approach:

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>

Output:

8
1024

Time complexity: O(logn) for given number n

Space complexity: O(1) since using constant variables

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!