Count numbers up to N having digit D in its octal representation
Given a positive integer N and an integer D representing a digit, the task is to count the numbers in the range[1, N] such that at least one digit in octal representation of the number is d.
Examples:
Input: N = 20, D = 7
Output: 2
Explanation:
The numbers in the range [1, 20] having digit 7 in their octal representation are 7 and 15.
Therefore, the required output is 2.Input: N = 40, D = 5
Output: 6
Explanation:
The numbers in the range [1, 40] having digit 5 in their octal representation are 5, 13, 21, 29, 37, and 40.
Therefore, the required output is 6
Approach: Follow the steps below to solve the problem:
- Iterate over the range [1, N]. For every ith number check if at least one digit in octal representation of the number is d or not. If found to be true, then increment the count.
- Finally, print the count obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count the numbers in given // range whose octal representation // contains atleast digit, d void countNumbers( int n, int d) { // Store count of numbers up to n // whose octal representation // contains digit d int total = 0; // Iterate over the range[1, n] for ( int i = 1; i <= n; i++) { int x = i; // Calculate digit of i in // octal representation while (x > 0) { // Check if octal representation // of x contains digit d if (x % 8 == d) { // Update total total++; break ; } // Update x x = x / 8; } } // Print the answer cout << total; } // Driver Code int main() { // Given N and D int n = 20, d = 7; // Counts and prints numbers // up to N having D as a digit // in its octal representation countNumbers(n, d); return 0; } |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ // Function to count the numbers in given // range whose octal representation // contains atleast digit, d static void countNumbers( int n, int d) { // Store count of numbers up to n // whose octal representation // contains digit d int total = 0 ; // Iterate over the range[1, n] for ( int i = 1 ; i <= n; i++) { int x = i; // Calculate digit of i in // octal representation while (x > 0 ) { // Check if octal representation // of x contains digit d if (x % 8 == d) { // Update total total++; break ; } // Update x x = x / 8 ; } } // Print the answer System.out.println(total); } // Driver code public static void main(String[] args) { // Given N and D int n = 20 , d = 7 ; // Counts and prints numbers // up to N having D as a digit // in its octal representation countNumbers(n, d); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program to implement # the above approach # Function to count the numbers in given # range whose octal representation # contains atleast digit, d def countNumbers(n, d): # Store count of numbers up to n # whose octal representation # contains digit d total = 0 # Iterate over the range[1, n] for i in range ( 1 , n + 1 ): x = i # Calculate digit of i in # octal representation while (x > 0 ): # Check if octal representation # of x contains digit d if (x % 8 = = d): # Update total total + = 1 break # Update x x = x / / 8 # Print the answer print (total) # Driver Code if __name__ = = '__main__' : # Given N and D n , d = 20 , 7 # Counts and prints numbers # up to N having D as a digit # in its octal representation countNumbers(n, d) # This code is contributed by mohit kumr 29 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to count the numbers in given // range whose octal representation // contains atleast digit, d static void countNumbers( int n, int d) { // Store count of numbers up to n // whose octal representation // contains digit d int total = 0; // Iterate over the range[1, n] for ( int i = 1; i <= n; i++) { int x = i; // Calculate digit of i in // octal representation while (x > 0) { // Check if octal representation // of x contains digit d if (x % 8 == d) { // Update total total++; break ; } // Update x x = x / 8; } } // Print the answer Console.WriteLine(total); } // Driver Code static void Main() { // Given N and D int n = 20, d = 7; // Counts and prints numbers // up to N having D as a digit // in its octal representation countNumbers(n, d); } } // This code is contributed by susmitakundugoaldanga |
Javascript
<script> // Javascript program to implement // the above approach // Function to count the numbers in given // range whose octal representation // contains atleast digit, d function countNumbers(n, d) { // Store count of numbers up to n // whose octal representation // contains digit d let total = 0; // Iterate over the range[1, n] for (let i = 1; i <= n; i++) { let x = i; // Calculate digit of i in // octal representation while (x > 0) { // Check if octal representation // of x contains digit d if (x % 8 == d) { // Update total total++; break ; } // Update x x = x / 8; } } // Print the answer document.write(total); } // Driver Code // Given N and D let n = 20, d = 7; // Counts and prints numbers // up to N having D as a digit // in its octal representation countNumbers(n, d); // This code is contributed by souravghosh0416. </script> |
Output:
2
Time Complexity: O(N * log8N)
Auxiliary Space: O(1)