Count of Octal numbers upto N digits

0 0 3 minutes read

Given an integer N, the task is to find the count of natural octal numbers up to N digits.

Examples:
Input: N = 1
Output: 7
Explanation:
1, 2, 3, 4, 5, 6, 7 are 1 digit Natural Octal numbers.
Input: N = 2
Output: 63
Explanation:
There are a total of 56 two digit octal numbers and 7 one digit octal numbers. Therefore, 56 + 7 = 63.

Approach: On observing carefully, a geometric progression series is formed [ 7 56 448 3584 28672 229376… ] with the first term being 7 and a common ratio of 8.
Therefore,

Nth term = Number of Octal numbers of N digits = 7 * 8^{N - 1}

Finally, count of all octal numbers up to N digits can be found out by iterating a loop from 1 to N and calculating the sum of ith term using the above formula.
Below is the implementation of the above approach:

C++

// C++ program to find the count of
// natural octal numbers upto N digits
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// natural octal numbers upto N digits
int count(int N)
{
    int sum = 0;
 
    // Loop to iterate from 1 to N
    // and calculating number of
    // octal numbers for every 'i'th digit.
    for (int i = 1; i <= N; i++) {
        sum += 7 * pow(8, i - 1);
    }
    return sum;
}
 
// Driver code
int main()
{
    int N = 4;
    cout << count(N);
 
    return 0;
}

Java

// Java program to find the count of 
// natural octal numbers upto N digits 
 
public class GFG {
     
    // Function to return the count of 
    // natural octal numbers upto N digits 
    static int count(int N) 
    { 
        int sum = 0; 
     
        // Loop to iterate from 1 to N 
        // and calculating number of 
        // octal numbers for every 'i'th digit. 
        for (int i = 1; i <= N; i++) { 
            sum += 7 * Math.pow(8, i - 1); 
        } 
        return sum; 
    } 
     
    // Driver code 
    public static void main (String[] args) 
    { 
        int N = 4; 
        System.out.println(count(N)); 
     
    } 
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 program to find the count of 
# natural octal numbers upto N digits 
 
# Function to return the count of 
# natural octal numbers upto N digits 
def count(N) : 
 
    sum = 0; 
 
    # Loop to iterate from 1 to N 
    # and calculating number of 
    # octal numbers for every 'i'th digit. 
    for i in range(N + 1) :
        sum += 7 * (8 **(i - 1)); 
     
    return int(sum);
 
# Driver code 
if __name__ == "__main__" : 
 
    N = 4; 
    print(count(N)); 
 
# This code is contributed by AnkitRai01

C#

// C# program to find the count of 
// natural octal numbers upto N digits 
using System;
 
class GFG
{
     
    // Function to return the count of 
    // natural octal numbers upto N digits 
    static int count(int N) 
    { 
        int sum = 0; 
     
        // Loop to iterate from 1 to N 
        // and calculating number of 
        // octal numbers for every 'i'th digit. 
        for (int i = 1; i <= N; i++)
        { 
            sum += (int)(7 * Math.Pow(8, i - 1)); 
        } 
        return sum; 
    } 
     
    // Driver code 
    public static void Main ()
    { 
        int N = 4; 
        Console.WriteLine(count(N)); 
    } 
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
 
// Javascript program to find the count of
// natural octal numbers upto N digits
 
// Function to return the count of
// natural octal numbers upto N digits
function count(N)
{
    var sum = 0;
 
    // Loop to iterate from 1 to N
    // and calculating number of
    // octal numbers for every 'i'th digit.
    for (var i = 1; i <= N; i++) {
        sum += 7 * Math.pow(8, i - 1);
    }
    return sum;
}
 
// Driver code
 var N = 4;
 document.write(count(N));
 
 
</script>

Output:

Time Complexity: O(N*logN) because using inbuilt pow function in loop, time complexity of pow function is logN

Auxiliary Space: O(1)

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!