Find the occurrences of digit d in the range [0..n]
Given a number n and a digit d, count all occurrences of d in range from 0 to n.
Examples:
Input : n = 25
d = 2
Output : 9
The occurrences are 2, 12, 20, 21
22 (Two occurrences), 23, 24, 25
Input : n = 25
d = 3
Output :3
The occurrences are 3, 13, 23
Input : n = 32
d = 3
Output : 6
The occurrences are 3, 13, 23, 30, 31, 32
This solution is based on the modularity of each digit at its position in the number.
This modularity is calculated from the power of 10 related to the position in the number in empirical method.
C++
#include <iostream> #include <math.h> using namespace std; int myCountX( int N, int X) { int x, a, r; int e; // The loop is executed for every digit of N e = ( int )( log10 (N)); r = 0; while (e >= 0) { // Calculation of next digit in decrescent order of // power of 10 x = N / ( int ) pow (10, e); x %= 10; // Modularity based on power of 10 a = x * e * ( int ) pow (10, e - 1); r += a; // If the digit is the searched one then the // remainder of division by the current power of 10 // is added to result because a number of occurances // equal to this remainder is when the digit is // present with this position if (x == X) { a = (N % ( int ) pow (10, e)) + 1; // But if the searched digit is equal to 0 then // there aren't number with the most significant // digit equal to 0 if (X == 0) a -= ( int ) pow (10, e); r += a; } // If the digit is greater than the searched one and // the searched digit isn't 0 then the number of all // number with the most significat digit equal to // the searched one must be added to result if (x > X && X != 0) { a = ( int ) pow (10, e); r += a; } e--; } return r; } int main() { int N, X; N = 1000; X = 0; cout << myCountX(N, X); return 0; } |
Java
import java.util.Scanner; public class Main { static int myCountX( int N, int X) { int x, a, r; int e; // The loop is executed for every digit of N e = ( int ) (Math.log10(N)); r = 0 ; while (e >= 0 ) { // Calculation of the next digit in decreasing order of power of 10 x = N / ( int ) Math.pow( 10 , e); x %= 10 ; // Modularity based on the power of 10 a = x * e * ( int ) Math.pow( 10 , e - 1 ); r += a; // If the digit is the searched one, then the remainder of // the division by the current power of 10 // is added to the result because a number of occurrences equal // to this remainder is when the digit is present with this position if (x == X) { a = (N % ( int ) Math.pow( 10 , e)) + 1 ; // But if the searched digit is equal to 0 then there aren't // numbers with the most significant // digit equal to 0 if (X == 0 ) a -= ( int ) Math.pow( 10 , e); r += a; } // If the digit is greater than the searched one and // the searched digit isn't 0 then the number of all // numbers with the most significant digit equal to // the searched one must be added to the result if (x > X && X != 0 ) { a = ( int ) Math.pow( 10 , e); r += a; } e--; } return r; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N, X; N = 1000 ; X = 0 ; System.out.println(myCountX(N, X)); scanner.close(); } } |
Python3
import math def myCountX(N, X): e = int (math.log10(N)) r = 0 while e > = 0 : x = N / / 10 * * e % 10 a = x * e * 10 * * (e - 1 ) r + = a if x = = X: a = N % 10 * * e + 1 if X = = 0 : a - = 10 * * e r + = a if x > X and X ! = 0 : a = 10 * * e r + = a e - = 1 return r if __name__ = = "__main__" : N = 1000 X = 0 print (myCountX(N, X)) # Output: 192 |
C#
using System; class Program { static int MyCountX( int N, int X) { int x, a, r; int e; // The loop is executed for every digit of N e = ( int )Math.Log10(N); r = 0; while (e >= 0) { // Calculation of the next digit in decreasing order of power of 10 x = N / ( int )Math.Pow(10, e); x %= 10; // Modularity based on power of 10 a = x * e * ( int )Math.Pow(10, e - 1); r += a; // If the digit is the searched one, then the remainder of division by // the current power of 10 is added to the result because a number of // occurrences equal to this remainder is when the digit is present with // this position if (x == X) { a = (N % ( int )Math.Pow(10, e)) + 1; // But if the searched digit is equal to 0, then there aren't numbers // with the most significant digit equal to 0 if (X == 0) a -= ( int )Math.Pow(10, e); r += a; } // If the digit is greater than the searched one and the searched digit // isn't 0, then the number of all numbers with the most significant digit // equal to the searched one must be added to the result if (x > X && X != 0) { a = ( int )Math.Pow(10, e); r += a; } e--; } return r; } static void Main() { int N, X; N = 1000; X = 0; Console.WriteLine(MyCountX(N, X)); } } |
Javascript
function myCountX(N, X) { let x, a, r; let e; // The loop is executed for every digit of N e = Math.floor(Math.log10(N)); r = 0; while (e >= 0) { // Calculation of the next digit in decreasing order of power of 10 x = Math.floor(N / Math.pow(10, e)); x %= 10; // Modularity based on the power of 10 a = x * e * Math.pow(10, e - 1); r += a; // If the digit is the searched one, then the remainder of // the division by the current power of 10 // is added to the result because a number of occurrences equal // to this remainder is when the digit is present with this position if (x === X) { a = (N % Math.pow(10, e)) + 1; // But if the searched digit is equal to 0 then there aren't // numbers with the most significant // digit equal to 0 if (X === 0) a -= Math.pow(10, e); r += a; } // If the digit is greater than the searched one and // the searched digit isn't 0 then the number of all // numbers with the most significant digit equal to // the searched one must be added to the result if (x > X && X !== 0) { a = Math.pow(10, e); r += a; } e--; } return r; } function main() { let N, X; N = 1000; X = 0; console.log(myCountX(N, X)); } main(); |
Output:
192
Time Complexity : O(logn)
Auxiliary Space : O(1)
This article is contributed by Antonio D’Angelico (CODERLOVER).