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 termint getValue(int n){ int i = 0, k = 1; while (i < n) { i = i + k; k = k * 2; } return k / 2;}// Driver Codeint 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 termclass 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 termusing 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 termfunction 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> |
8 1024
Time Complexity: O(n / k)
Auxiliary Space: O(1)
Efficient Approach: This Problem can be solved in O(1) time complexity.
Let nth term of the sequence be equal to 2m
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 termint getValue(int n){ // Find log of n+1 on base 2 int result = (floor)(log(n + 1) / log(2)); return pow(2, result);}// Driver Codeint 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 termimport java.lang.*;import java.lang.Math;import java.io.*;class GFG { // Function that will return nth termstatic 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 termimport math# Function that will return nth termdef 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 coden = 9print(getValue(n))n = 1025print(getValue(n))# This code is contributed # by Shrikant13 |
C#
// C# Program to find Nth termusing 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 termfunction 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 valueecho getValue($n), "\n";// Get n$n = 1025;// Get the valueecho getValue($n), "\n";// This code is contributed by ajit?> |
Javascript
<script> // Javascript Program to find Nth term// Function that will return nth termfunction 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 nlet n = 9;// Get the valuedocument.write(getValue(n) + "<br>");// Get nn = 1025;// Get the valuedocument.write(getValue(n));// This code is contributed by subhammahato348.</script> |
8 1024
Time complexity: O(logn) for given number n
Space complexity: O(1) since using constant variables
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

