Given a number n, find count of all numbers from 1 to n that have 4 as a digit.
Examples :
Input: n = 5 Output: 1 Only 4 has '4' as digit Input: n = 50 Output: 14 Input: n = 328 Output: 60
This problem is mainly a variation of previous article on Compute sum of digits in all numbers from 1 to n.
Naive Solution: A naive solution is to go through every number x from 1 to n, and check if x has 4. To check if x has or not, we can traverse all digits of x. Below is the implementation of above idea:
Implementation:
C++
// A Simple C++ program to compute sum of digits in numbers from 1 to n#include<iostream>using namespace std;bool has4(int x);// Returns sum of all digits in numbers from 1 to nint countNumbersWith4(int n){ int result = 0; // initialize result // One by one compute sum of digits in every number from // 1 to n for (int x=1; x<=n; x++) result += has4(x)? 1 : 0; return result;}// A utility function to compute sum of digits in a// given number xbool has4(int x){ while (x != 0) { if (x%10 == 4) return true; x = x /10; } return false;}// Driver Programint main(){ int n = 328; cout << "Count of numbers from 1 to " << n << " that have 4 as a digit is " << countNumbersWith4(n) << endl; return 0;} |
Java
// Java program to compute sum of// digits in numbers from 1 to nimport java.io.*;class GFG { // Returns sum of all digits // in numbers from 1 to n static int countNumbersWith4(int n) { // initialize result int result = 0; // One by one compute sum of digits // in every number from 1 to n for (int x=1; x<=n; x++) result += has4(x)? 1 : 0; return result; } // A utility function to compute sum // of digits in a given number x static boolean has4(int x) { while (x != 0) { if (x%10 == 4) return true; x = x /10; } return false; } // Driver Program public static void main(String args[]) { int n = 328; System.out.println("Count of numbers from 1 to " + " that have 4 as a digit is " + countNumbersWith4(n)) ; }}// This code is contributed by Nikita Tiwari. |
Python3
# A Simple Python 3 program to compute# sum of digits in numbers from 1 to n# Returns sum of all digits in numbers from 1 to ndef countNumbersWith4(n) : result = 0 # initialize result # One by one compute sum of digits # in every number from 1 to n for x in range(1, n + 1) : if(has4(x) == True) : result = result + 1 return result# A utility function to compute sum # of digits in a given number xdef has4(x) : while (x != 0) : if (x%10 == 4) : return True x = x //10 return False # Driver Programn = 328print ("Count of numbers from 1 to ", n, " that have 4 as a digit is ", countNumbersWith4(n)) # This code is contributed by Nikita Tiwari. |
C#
// C# program to compute sum of// digits in numbers from 1 to nusing System;public class GFG { // Returns sum of all digits // in numbers from 1 to n static int countNumbersWith4(int n) { // initialize result int result = 0; // One by one compute sum of digits // in every number from 1 to n for (int x = 1; x <= n; x++) result += has4(x) ? 1 : 0; return result; } // A utility function to compute sum // of digits in a given number x static bool has4(int x) { while (x != 0) { if (x % 10 == 4) return true; x = x / 10; } return false; } // Driver Code public static void Main() { int n = 328; Console.WriteLine("Count of numbers from 1 to " + " that have 4 as a digit is " + countNumbersWith4(n)) ; }}// This code is contributed by Sam007 |
PHP
<?php// PHP program to compute sum of// digits in numbers from 1 to n// Returns sum of all digits // in numbers from 1 to nfunction countNumbersWith4($n){ $result = 0; // initialize result // One by one compute sum of // digits in every number from 1 to n for ($x = 1; $x <= $n; $x++) $result += has4($x) ? 1 : 0; return $result;}// A utility function to compute // sum of digits in a given number xfunction has4($x){ while ($x != 0) { if ($x % 10 == 4) return true; $x = intval($x / 10); } return false;}// Driver Code$n = 328;echo "Count of numbers from 1 to " . $n . " that have 4 as a digit is " . countNumbersWith4($n); // This code is contributed by Sam007?> |
Javascript
<script>// Javascript program to compute sum of// digits in numbers from 1 to n// Returns sum of all digits// in numbers from 1 to nfunction countNumbersWith4(n){ // Initialize result let result = 0; // One by one compute sum of digits // in every number from 1 to n for(let x = 1; x <= n; x++) result += has4(x) ? 1 : 0; return result;}// A utility function to compute sum// of digits in a given number xfunction has4(x){ while (x != 0) { if (x % 10 == 4) return true; x = Math.floor(x / 10); } return false;}// Driver codelet n = 328;document.write("Count of numbers from 1 to " + n + " that have 4 as a digit is " + countNumbersWith4(n)) ;// This code is contributed by avanitrachhadiya2155 </script> |
Output
Count of numbers from 1 to 328 that have 4 as a digit is 60
Time Complexity: O(N log N) ,as complexity of function countNumbersWith4(int n) is O(N) and as it calling function has4(int x) N times whose complexity is O(log N) ,thus overall complexity is O(N log N).
Auxiliary Space: O(1), since no extra space used.
An Efficient Solution using DP: We can make above approach more efficient through DP (Dynamic Programming) using memoization technique. We can store the presence of 4 in the previous visited integers so that whenever we need to check those integers we don’t need to check whether it contains 4 or not by checking each digit again. To check we can simply check from the DP array.
Implementation:
C++
#include <iostream>using namespace std;bool contains(int i);int countNumberswith4(int N){ int count = 0; bool dp[N + 1] = { 0 }; // boolean dp array to store whether // the number contains digit '4' or not for (int i = 1; i <= N; i++) { if (dp[i]) { // if dp[i] is true that means // that number contains digit '4' count++; continue; // if it contains then no need to // check again hence continue } if (contains(i)) { // check if i contains digit '4' // or not count++; dp[i] = true; // if it contains then mark dp[i] as // true so that it can used later } } return count;}bool contains(int i) // boolean function to check{ // whether i contains digit '4' or not while (i > 0) { if (i % 10 == 4) return true; i /= 10; } return false;}int main(){ int n = 278; cout << "Count of numbers from 1 to " << n << " that have 4 as a digit is " << countNumberswith4(n) << endl; return 0;}// This code is contributed by Anurag Mishra |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { static int countNumberswith4(int N) { int count = 0; boolean dp[] = new boolean [N + 1]; // boolean dp array to store whether // the number contains digit '4' or not for (int i = 1; i <= N; i++) { if (dp[i]) { // if dp[i] is true that means // that number contains digit '4' count++; continue; // if it contains then no need to // check again hence continue } if (contains(i)) { // check if i contains digit // '4' or not count++; dp[i] = true; // if it contains then mark // dp[i] as true so that it // can used later } } return count; } static boolean contains(int i) // boolean function to check { // whether i contains digit '4' or not while (i > 0) { if (i % 10 == 4) return true; i /= 10; } return false; } public static void main(String[] args) { int n = 278; System.out.println("Count of numbers from 1 to " + n + " that have 4 as a digit is " + countNumberswith4(n)); }}// This code is contributed by Anurag Mishra |
Python3
def contains(i): # boolean function to check # whether i contains digit '4' or not while (i > 0): if (i % 10 == 4): return True i = i // 10 return Falsedef countNumberswith4(N): count = 0 dp = [0 for i in range(N + 1)] # boolean dp array to store whether # the number contains digit '4' or not for i in range(1,N + 1): if (dp[i]): # if dp[i] is true that means # that number contains digit '4' count += 1 continue # if it contains then no need to # check again hence continue if (contains(i)): # check if i contains digit '4' # or not count += 1 dp[i] = True # if it contains then mark dp[i] as # true so that it can used later return count# driver coden = 278print(f"Count of numbers from 1 to {n} that have 4 as a digit is {countNumberswith4(n)}")# This code is contributed by shinjanpatra |
C#
// C# program to find largest number// smaller than equal to n with all prime digits.using System;class GFG { static bool contains(int i) // boolean function to check { // whether i contains digit '4' or not while (i > 0) { if (i % 10 == 4) return true; i /= 10; } return false; } static int countNumberswith4(int N) { int count = 0; bool[] dp = new bool[N + 1]; for (int i = 0; i < dp.Length; i++) { dp[i] = false; } // boolean dp array to store whether // the number contains digit '4' or not for (int i = 1; i <= N; i++) { if (dp[i]) { // if dp[i] is true that means // that number contains digit '4' count++; continue; // if it contains then no need to // check again hence continue } if (contains(i)) { // check if i contains digit // '4' or not count++; dp[i] = true; // if it contains then mark // dp[i] as true so that it // can used later } } return count; } // Driver code static void Main() { int n = 278; Console.WriteLine("Count of numbers from 1 to " + n + " that have 4 as a digit is " + countNumberswith4(n)); }}// The code is contributed by Nidhi goel |
Javascript
<script>function contains(i){ // boolean function to check // whether i contains digit '4' or not while (i > 0){ if (i % 10 == 4) return true i = Math.floor(i/10) } return false}function countNumberswith4(N){ let count = 0 let dp = new Array(N+1).fill(0) // boolean dp array to store whether // the number contains digit '4' or not for(let i=1;i<N+1;i++){ if (dp[i]){ // if dp[i] is true that means // that number contains digit '4' count += 1 continue // if it contains then no need to // check again hence continue } if (contains(i)){ // check if i contains digit '4' // or not count += 1 dp[i] = true // if it contains then mark dp[i] as // true so that it can used later } } return count}// driver codelet n = 278document.write(`Count of numbers from 1 to {n} that have 4 as a digit is ${countNumberswith4(n)}`,"</br>")// This code is contributed by shinjanpatra</script> |
Output
Count of numbers from 1 to 278 that have 4 as a digit is 55
Time complexity : O(n log n)
Space complexity : O(n)
Another Efficient Solution:
Above first solution is a naive solution. We can do it more efficiently by finding a pattern.
Let us take few examples.
Count of numbers from 0 to 9 = 1 Count of numbers from 0 to 99 = 1*9 + 10 = 19 Count of numbers from 0 to 999 = 19*9 + 100 = 271 In general, we can write count(10d) = 9 * count(10d - 1) + 10d - 1
In below implementation, the above formula is implemented using dynamic programming as there are overlapping subproblems.
The above formula is one core step of the idea. Below is complete algorithm.
1) Find number of digits minus one in n. Let this value be 'd'.
For 328, d is 2.
2) Compute some of digits in numbers from 1 to 10d - 1.
Let this sum be w. For 328, we compute sum of digits from 1 to
99 using above formula.
3) Find Most significant digit (msd) in n. For 328, msd is 3.
4.a) If MSD is 4. For example if n = 428, then count of
numbers is sum of following.
1) Count of numbers from 1 to 399
2) Count of numbers from 400 to 428 which is 29.
4.b) IF MSD > 4. For example if n is 728, then count of
numbers is sum of following.
1) Count of numbers from 1 to 399 and count of numbers
from 500 to 699, i.e., "a[2] * 6"
2) Count of numbers from 400 to 499, i.e. 100
3) Count of numbers from 700 to 728, recur for 28
4.c) IF MSD < 4. For example if n is 328, then count of
numbers is sum of following.
1) Count of numbers from 1 to 299 a
2) Count of numbers from 300 to 328, recur for 28
Below is implementation of above algorithm.
C++
// C++ program to count numbers having 4 as a digit#include<bits/stdc++.h>using namespace std;// Function to count numbers from 1 to n that have// 4 as a digitint countNumbersWith4(int n){ // Base case if (n < 4) return 0; // d = number of digits minus one in n. For 328, d is 2 int d = log10(n); // computing count of numbers from 1 to 10^d-1, // d=0 a[0] = 0; // d=1 a[1] = count of numbers from 0 to 9 = 1 // d=2 a[2] = count of numbers from 0 to 99 = a[1]*9 + 10 = 19 // d=3 a[3] = count of numbers from 0 to 999 = a[2]*19 + 100 = 171 int *a = new int[d+1]; a[0] = 0, a[1] = 1; for (int i=2; i<=d; i++) a[i] = a[i-1]*9 + ceil(pow(10,i-1)); // Computing 10^d int p = ceil(pow(10, d)); // Most significant digit (msd) of n, // For 328, msd is 3 which can be obtained using 328/100 int msd = n/p; // If MSD is 4. For example if n = 428, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 399 // 2) Count of numbers from 400 to 428 which is 29. if (msd == 4) return (msd)*a[d] + (n%p) + 1; // IF MSD > 4. For example if n is 728, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 399 and count of numbers // from 500 to 699, i.e., "a[2] * 6" // 2) Count of numbers from 400 to 499, i.e. 100 // 3) Count of numbers from 700 to 728, recur for 28 if (msd > 4) return (msd-1)*a[d] + p + countNumbersWith4(n%p); // IF MSD < 4. For example if n is 328, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 299 a // 2) Count of numbers from 300 to 328, recur for 28 return (msd)*a[d] + countNumbersWith4(n%p);}// Driver Programint main(){ int n = 328; cout << "Count of numbers from 1 to " << n << " that have 4 as a digit is " << countNumbersWith4(n) << endl; return 0;} |
Java
// Java program to count numbers having 4 as a digitclass GFG{ // Function to count numbers from// 1 to n that have 4 as a digitstatic int countNumbersWith4(int n){ // Base case if (n < 4) return 0; // d = number of digits minus // one in n. For 328, d is 2 int d = (int)Math.log10(n); // computing count of numbers from 1 to 10^d-1, // d=0 a[0] = 0; // d=1 a[1] = count of numbers from // 0 to 9 = 1 // d=2 a[2] = count of numbers from // 0 to 99 = a[1]*9 + 10 = 19 // d=3 a[3] = count of numbers from // 0 to 999 = a[2]*19 + 100 = 171 int[] a = new int[d + 2]; a[0] = 0; a[1] = 1; for (int i = 2; i <= d; i++) a[i] = a[i - 1] * 9 + (int)Math.ceil(Math.pow(10, i - 1)); // Computing 10^d int p = (int)Math.ceil(Math.pow(10, d)); // Most significant digit (msd) of n, // For 328, msd is 3 which can be obtained using 328/100 int msd = n / p; // If MSD is 4. For example if n = 428, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 399 // 2) Count of numbers from 400 to 428 which is 29. if (msd == 4) return (msd) * a[d] + (n % p) + 1; // IF MSD > 4. For example if n // is 728, then count of numbers // is sum of following. // 1) Count of numbers from 1 to // 399 and count of numbers from // 500 to 699, i.e., "a[2] * 6" // 2) Count of numbers from 400 // to 499, i.e. 100 // 3) Count of numbers from 700 to // 728, recur for 28 if (msd > 4) return (msd - 1) * a[d] + p + countNumbersWith4(n % p); // IF MSD < 4. For example if n is 328, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 299 a // 2) Count of numbers from 300 to 328, recur for 28 return (msd) * a[d] + countNumbersWith4(n % p);}// Driver codepublic static void main (String[] args) { int n = 328; System.out.println("Count of numbers from 1 to "+ n + " that have 4 as a digit is " + countNumbersWith4(n));}}// This code is contributed by chandan_jnu |
Python3
# Python3 program to count numbers having 4 as a digitimport math as mt# Function to count numbers from 1 to n # that have 4 as a digitdef countNumbersWith4(n): # Base case if (n < 4): return 0 # d = number of digits minus one in n. # For 328, d is 2 d = int(mt.log10(n)) # computing count of numbers from 1 to 10^d-1, # d=0 a[0] = 0 # d=1 a[1] = count of numbers from 0 to 9 = 1 # d=2 a[2] = count of numbers from # 0 to 99 = a[1]*9 + 10 = 19 # d=3 a[3] = count of numbers from # 0 to 999 = a[2]*19 + 100 = 171 a = [1 for i in range(d + 1)] a[0] = 0 if len(a) > 1: a[1] = 1 for i in range(2, d + 1): a[i] = a[i - 1] * 9 + mt.ceil(pow(10, i - 1)) # Computing 10^d p = mt.ceil(pow(10, d)) # Most significant digit (msd) of n, # For 328, msd is 3 which can be # obtained using 328/100 msd = n // p # If MSD is 4. For example if n = 428, # then count of numbers is sum of following. # 1) Count of numbers from 1 to 399 # 2) Count of numbers from 400 to 428 which is 29. if (msd == 4): return (msd) * a[d] + (n % p) + 1 # IF MSD > 4. For example if n is 728, # then count of numbers is sum of following. # 1) Count of numbers from 1 to 399 and count # of numbers from 500 to 699, i.e., "a[2] * 6" # 2) Count of numbers from 400 to 499, i.e. 100 # 3) Count of numbers from 700 to 728, recur for 28 if (msd > 4): return ((msd - 1) * a[d] + p + countNumbersWith4(n % p)) # IF MSD < 4. For example if n is 328, # then count of numbers is sum of following. # 1) Count of numbers from 1 to 299 a # 2) Count of numbers from 300 to 328, recur for 28 return (msd) * a[d] + countNumbersWith4(n % p)# Driver Coden = 328print("Count of numbers from 1 to", n, "that have 4 as a digit is", countNumbersWith4(n)) # This code is contributed by mohit kumar 29 |
C#
// C# program to count numbers having 4 as a digitusing System;class GFG{// Function to count numbers from// 1 to n that have 4 as a digitstatic int countNumbersWith4(int n){ // Base case if (n < 4) return 0; // d = number of digits minus // one in n. For 328, d is 2 int d = (int)Math.Log10(n); // computing count of numbers from 1 to 10^d-1, // d=0 a[0] = 0; // d=1 a[1] = count of numbers from // 0 to 9 = 1 // d=2 a[2] = count of numbers from // 0 to 99 = a[1]*9 + 10 = 19 // d=3 a[3] = count of numbers from // 0 to 999 = a[2]*19 + 100 = 171 int[] a = new int[d+2]; a[0] = 0; a[1] = 1; for (int i = 2; i <= d; i++) a[i] = a[i - 1] * 9 + (int)Math.Ceiling(Math.Pow(10, i - 1)); // Computing 10^d int p = (int)Math.Ceiling(Math.Pow(10, d)); // Most significant digit (msd) of n, // For 328, msd is 3 which can be obtained using 328/100 int msd = n / p; // If MSD is 4. For example if n = 428, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 399 // 2) Count of numbers from 400 to 428 which is 29. if (msd == 4) return (msd) * a[d] + (n % p) + 1; // IF MSD > 4. For example if n is 728, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 399 and count of numbers // from 500 to 699, i.e., "a[2] * 6" // 2) Count of numbers from 400 to 499, i.e. 100 // 3) Count of numbers from 700 to 728, recur for 28 if (msd > 4) return (msd - 1) * a[d] + p + countNumbersWith4(n % p); // IF MSD < 4. For example if n is 328, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 299 a // 2) Count of numbers from 300 to 328, recur for 28 return (msd) * a[d] + countNumbersWith4(n % p);}// Driver codestatic void Main(){ int n = 328; Console.WriteLine("Count of numbers from 1 to "+ n + " that have 4 as a digit is " + countNumbersWith4(n));}}// This code is contributed by chandan_jnu |
PHP
<?php // PHP program to count numbers having // 4 as a digit// Function to count numbers from 1 to n// that have 4 as a digitfunction countNumbersWith4($n){ // Base case if ($n < 4) return 0; // d = number of digits minus one in n. // For 328, d is 2 $d = (int)log10($n); // computing count of numbers from 1 to 10^d-1, // d=0 a[0] = 0; // d=1 a[1] = count of numbers from 0 to 9 is 1 // d=2 a[2] = count of numbers from 0 to 99 is // a[1]*9 + 10 = 19 // d=3 a[3] = count of numbers from 0 to 999 is // a[2]*19 + 100 = 171 $a = array_fill(0, $d + 1, NULL); $a[0] = 0; $a[1] = 1; for ($i = 2; $i <= $d; $i++) $a[$i] = $a[$i - 1] * 9 + ceil(pow(10, $i - 1)); // Computing 10^d $p = ceil(pow(10, $d)); // Most significant digit (msd) of n, // For 328, msd is 3 which can be // obtained using 328/100 $msd = intval($n / $p); // If MSD is 4. For example if n = 428, // then count of numbers is sum of following. // 1) Count of numbers from 1 to 399 // 2) Count of numbers from 400 to 428 which is 29. if ($msd == 4) return ($msd) * $a[$d] + ($n % $p) + 1; // IF MSD > 4. For example if n is 728, // then count of numbers is sum of following. // 1) Count of numbers from 1 to 399 and // count of numbers from 500 to 699, i.e., "a[2] * 6" // 2) Count of numbers from 400 to 499, i.e. 100 // 3) Count of numbers from 700 to 728, recur for 28 if ($msd > 4) return ($msd - 1) * $a[$d] + $p + countNumbersWith4($n % $p); // IF MSD < 4. For example if n is 328, then // count of numbers is sum of following. // 1) Count of numbers from 1 to 299 a // 2) Count of numbers from 300 to 328, recur for 28 return ($msd) * $a[$d] + countNumbersWith4($n % $p);}// Driver Code$n = 328;echo "Count of numbers from 1 to " . $n . " that have 4 as a digit is " . countNumbersWith4($n) . "\n";// This code is contributed by ita_c?> |
Javascript
<script>// Javascript program to count numbers having 4 as a digit // Function to count numbers from // 1 to n that have 4 as a digit function countNumbersWith4(n) { // Base case if (n < 4) return 0; // d = number of digits minus // one in n. For 328, d is 2 let d = Math.floor(Math.log10(n)); // computing count of numbers from 1 to 10^d-1, // d=0 a[0] = 0; // d=1 a[1] = count of numbers from // 0 to 9 = 1 // d=2 a[2] = count of numbers from // 0 to 99 = a[1]*9 + 10 = 19 // d=3 a[3] = count of numbers from // 0 to 999 = a[2]*19 + 100 = 171 let a = new Array(d + 2); for(let i=0;i<d+2;i++) { a[i]=0; } a[0] = 0; a[1] = 1; for (let i = 2; i <= d; i++) a[i] = a[i - 1] * 9 + Math.floor(Math.ceil(Math.pow(10, i - 1))); // Computing 10^d let p = Math.floor(Math.ceil(Math.pow(10, d))); // Most significant digit (msd) of n, // For 328, msd is 3 which can be obtained using 328/100 let msd = Math.floor(n / p); // If MSD is 4. For example if n = 428, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 399 // 2) Count of numbers from 400 to 428 which is 29. if (msd == 4) return (msd) * a[d] + (n % p) + 1; // IF MSD > 4. For example if n // is 728, then count of numbers // is sum of following. // 1) Count of numbers from 1 to // 399 and count of numbers from // 500 to 699, i.e., "a[2] * 6" // 2) Count of numbers from 400 // to 499, i.e. 100 // 3) Count of numbers from 700 to // 728, recur for 28 if (msd > 4) return (msd - 1) * a[d] + p + countNumbersWith4(n % p); // IF MSD < 4. For example if n is 328, then count of // numbers is sum of following. // 1) Count of numbers from 1 to 299 a // 2) Count of numbers from 300 to 328, recur for 28 return (msd) * a[d] + countNumbersWith4(n % p); } // Driver code let n = 328; document.write("Count of numbers from 1 to "+ n + " that have 4 as a digit is " + countNumbersWith4(n)); // This code is contributed by rag2127</script> |
Output
Count of numbers from 1 to 328 that have 4 as a digit is 60
Time complexity : O(log n)
space complexity : O(log n)
This article is contributed by Shivam. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
