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 * 8N - 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 digitsint 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 codeint 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 digitsfunction 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> |
4095
Time Complexity: O(N*logN) because using inbuilt pow function in loop, time complexity of pow function is logN
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
