Total no of 1’s in numbers
Given an integer n, count the total number of digits 1 appearing in all positive integers less than or equal to n.
Examples:
Input : n = 13
Output: 6
Explanation:
Here, no <= 13 containing 1 are 1, 10, 11, 12, 13. So, total 1s are 6.Input : n = 5
Output: 1
Explanation:
Here, no <= 13 containing 1 is 1. So, the total 1s are 1.
Approach 1:
- Iterate over i from 1 to n.
- Convert i to string and count ’1’ in each integer string.
- Add a count of ’1’ in each string to the sum.
Below is the implementation of the above approach:
C++
// c++ code to count the frequency of 1 // in numbers less than or equal to // the given number. #include <bits/stdc++.h> using namespace std; int countDigitOne( int n) { int countr = 0; for ( int i = 1; i <= n; i++) { string str = to_string(i); countr += count(str.begin(), str.end(), '1' ); } return countr; } // driver function int main() { int n = 13; cout << countDigitOne(n) << endl; n = 131; cout << countDigitOne(n) << endl; n = 159; cout << countDigitOne(n) << endl; return 0; } |
Java
// Java code to count the frequency of 1 // in numbers less than or equal to // the given number. class GFG { static int countDigitOne( int n) { int countr = 0 ; for ( int i = 1 ; i <= n; i++) { String str = String.valueOf(i); countr += str.split( "1" , - 1 ) . length - 1 ; } return countr; } // Driver Code public static void main(String[] args) { int n = 13 ; System.out.println(countDigitOne(n)); n = 131 ; System.out.println(countDigitOne(n)); n = 159 ; System.out.println(countDigitOne(n)); } } // This code is contributed by mits |
Python3
# Python3 code to count the frequency # of 1 in numbers less than or equal # to the given number. def countDigitOne(n): countr = 0 ; for i in range ( 1 , n + 1 ): str1 = str (i); countr + = str1.count( "1" ); return countr; # Driver Code n = 13 ; print (countDigitOne(n)); n = 131 ; print (countDigitOne(n)); n = 159 ; print (countDigitOne(n)); # This code is contributed by mits |
C#
// C# code to count the frequency of 1 // in numbers less than or equal to // the given number. using System; class GFG { static int countDigitOne( int n) { int countr = 0; for ( int i = 1; i <= n; i++) { string str = i.ToString(); countr += str.Split( "1" ) . Length - 1; } return countr; } // Driver Code public static void Main() { int n = 13; Console.WriteLine(countDigitOne(n)); n = 131; Console.WriteLine(countDigitOne(n)); n = 159; Console.WriteLine(countDigitOne(n)); } } // This code is contributed by mits |
Javascript
<script> // Javascript code to count the frequency of 1 // in numbers less than or equal to // the given number. function countDigitOne(n) { let countr = 0; for (let i = 1; i <= n; i++) { let str = i.toString(); countr += str.split( "1" ) . length - 1; } return countr; } let n = 13; document.write(countDigitOne(n) + "</br>" ); n = 131; document.write(countDigitOne(n) + "</br>" ); n = 159; document.write(countDigitOne(n) + "</br>" ); </script> |
PHP
<?php // PHP code to count the frequency of 1 // in numbers less than or equal to // the given number. function countDigitOne( $n ) { $countr = 0; for ( $i = 1; $i <= $n ; $i ++) { $str = strval ( $i ); $countr += substr_count( $str , '1' ); } return $countr ; } // Driver Code $n = 13; echo countDigitOne( $n ) . "\n" ; $n = 131; echo countDigitOne( $n ) . "\n" ; $n = 159; echo countDigitOne( $n ) . "\n" ; // This code is contributed by mits ?> |
6 66 96
Time complexity: O(nlog(n))
Approach 2:
- Initialize countr as 0.
- Iterate over i from 1 to n incrementing by 10 each time.
- Add (n / (i * 10 ) ) * i to countr after each (i*10) interval.
- Add min( max(n mod (i*10) – i + 1, 0), i) to countr.
Below is the implementation of the above approach:
C++
// c++ code to count the frequency of 1 // in numbers less than or equal to // the given number. #include <bits/stdc++.h> using namespace std; // function to count the frequency of 1. int countDigitOne( int n) { int countr = 0; for ( int i = 1; i <= n; i *= 10) { int divider = i * 10; countr += (n / divider) * i + min(max(n % divider - i + 1, 0), i); } return countr; } // driver function int main() { int n = 13; cout << countDigitOne(n) << endl; n = 113; cout << countDigitOne(n) << endl; n = 205; cout << countDigitOne(n) << endl; } |
Java
/// Java code to count the // frequency of 1 in numbers // less than or equal to // the given number. import java.io.*; class GFG { // function to count // the frequency of 1. static int countDigitOne( int n) { int countr = 0 ; for ( int i = 1 ; i <= n; i *= 10 ) { int divider = i * 10 ; countr += (n / divider) * i + Math.min(Math.max(n % divider - i + 1 , 0 ), i); } return countr; } // Driver Code public static void main (String[] args) { int n = 13 ; System.out.println(countDigitOne(n)); n = 113 ; System.out.println(countDigitOne(n)); n = 205 ; System.out.println(countDigitOne(n)); } } // This code is contributed by akt_mit |
Python3
# Python3 code to count the # frequency of 1 in numbers # less than or equal to # the given number. # function to count the # frequency of 1. def countDigitOne(n): countr = 0 ; i = 1 ; while (i < = n): divider = i * 10 ; countr + = ( int (n / divider) * i + min ( max (n % divider - i + 1 , 0 ), i)); i * = 10 ; return countr; # Driver Code n = 13 ; print (countDigitOne(n)); n = 113 ; print (countDigitOne(n)); n = 205 ; print (countDigitOne(n)); # This code is contributed by mits |
C#
// C# code to count the // frequency of 1 in numbers // less than or equal to // the given number. using System; class GFG { // function to count // the frequency of 1. static int countDigitOne( int n) { int countr = 0; for ( int i = 1; i <= n; i *= 10) { int divider = i * 10; countr += (n / divider) * i + Math.Min(Math.Max(n % divider - i + 1, 0), i); } return countr; } // Driver Code public static void Main() { int n = 13; Console.WriteLine(countDigitOne(n)); n = 113; Console.WriteLine(countDigitOne(n)); n = 205; Console.WriteLine(countDigitOne(n)); } } // This code is contributed by mits |
Javascript
<script> // Javascript code to count the frequency of 1 // in numbers less than or equal to // the given number. // function to count the frequency of 1. function countDigitOne(n) { var countr = 0; for ( var i = 1; i <= n; i *= 10) { var divider = i * 10; countr += parseInt(n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0), i); } return countr; } // driver function var n = 13; document.write(countDigitOne(n)+ "<br>" ); n = 113; document.write(countDigitOne(n)+ "<br>" ); n = 205; document.write(countDigitOne(n)+ "<br>" ); </script> |
PHP
<?php // PHP code to count the // frequency of 1 in numbers // less than or equal to // the given number. // function to count the // frequency of 1. function countDigitOne( $n ) { $countr = 0; for ( $i = 1; $i <= $n ; $i *= 10) { $divider = $i * 10; $countr += (int)( $n / $divider ) * $i + min(max( $n % $divider - $i + 1, 0), $i ); } return $countr ; } // Driver Code $n = 13; echo countDigitOne( $n ), "\n" ; $n = 113; echo countDigitOne( $n ), "\n" ; $n = 205; echo countDigitOne( $n ), "\n" ; // This code is contributed by ajit ?> |
6 40 141
Time complexity: O(log(n))
Maths behind calculating one
The intuition is to count the number of ones at all places i.e 1’s, 10’s, 100’s and so on. First, understand how the 1’s are appearing in numbers at different places
for one’s place,
0,1,2,3,4,5,6,7,8,9,10
number of 1 at one’s place is 1, similarly for
11,12,13,14,15,16,17,18,19,20 it is also 1
we can conclude that
0-10 count =1
11-20 count =1
21-30 count =1
now let’s see for ten’s place
10-20 count=10 for 11,12,13,14,15,16,17,18,19
100-110 count=1 for 110
111-120 count=10 for 111,112,113,114,115,116,117,118,119
Observations:
1. For one’s place, the range is of 10 numbers for which the count is 1.
2. For ten’s place, the range is of 100 numbers for which the count is 10, i.e. 11-20 count is 10, 111-120 count is 10
Example: n=235
the number of 1’s to be added for ones place for 235 should be:
0-10,11-20,21-30,31-40,41-50,51-60,61-70,71-80,81-90,91-100,101-110,111-120,121-130,131-140,………220-230,231-240
=(235/10)*1+add remaining 1’s for (231-240)
check for the tens place, let’s start the count from 11
10-20,110-120,210-220
=(235/100)*10+add remaining 1’s for (221-230, 231-240)
similarly for 100’s place
=(235/1000)*100+add remaining 1’s for (231-240)
now for the remaining additional part-
The remainder of the number will be having three cases
1. remainder is equal to zero, in this case, nothing will be added
2. remainder is greater than one, then the same factor by which we are multiplying the range will be added for example- for one’s place the factor is 1, for 10’s place the factor is 10, for 100’s place factor is 100, and so on.
3. remainder is equal to one, for example, let say 11 is the number and by applying the above method we will be calculating the ones from 11-20, so to ignore the extra counts of 1 this check is required where we can simply add n%factor+1,
Let’s understand the approach with the help of code
C++
// This program counts the number of occurrences of the // digit 1 in the range from 1 to a given number #include <bits/stdc++.h> using namespace std; // Function to calculate the number of occurrences of the // digit 1 in a given number int calculatedigitsOfone( int A) { int n = A, factors = 1, count = 0, remainder = 0; while (n > 0) { int temp = factors; // check for remainders three cases mentioned in // the approach if (n % 10 == 0) { remainder = 0; } else if (n % 10 > 1) { remainder = temp; } else if (n % 10 == 1) { remainder = (A % temp) + 1; } factors *= 10; // incrementing factors for checking // different locations such as ones, // tens,hundreds places ones count += (A / factors) * temp + remainder; n = n / 10; } return count; } // Driver code int main() { int n = 11; cout << calculatedigitsOfone(n) << endl; n = 113; cout << calculatedigitsOfone(n) << endl; n = 235; cout << calculatedigitsOfone(n) << endl; return 0; } // This code is contributed by user_dtewbxkn77n |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { static int calculatedigitsOfone( int A) { int n = A, factors = 1 , count = 0 , remainder = 0 ; while (n > 0 ) { int temp = factors; // check for remainders three cases mentioned in // the approach if (n % 10 == 0 ) { remainder = 0 ; } else if (n % 10 > 1 ) { remainder = temp; } else if (n % 10 == 1 ) { remainder = (A % temp) + 1 ; } factors *= 10 ; // increamneting factors for checking // different locations such as ones, // tens,hundreds places ones count += (A / factors) * temp + remainder; n = n / 10 ; } return count; } public static void main(String[] args) { int n = 11 ; System.out.println(calculatedigitsOfone(n)); n = 113 ; System.out.println(calculatedigitsOfone(n)); n = 235 ; System.out.println(calculatedigitsOfone(n)); } } |
Python3
def calculatedigitsOfone(A): n, factors, count, remainder = A, 1 , 0 , 0 while n > 0 : temp = factors # check for remainders three cases mentioned in # the approach if n % 10 = = 0 : remainder = 0 elif n % 10 > 1 : remainder = temp elif n % 10 = = 1 : remainder = (A % temp) + 1 factors * = 10 # incrementing factors for checking # different locations such as ones, # tens, hundreds places ones count + = (A / / factors) * temp + remainder n / / = 10 return count # Example usage n = 11 print (calculatedigitsOfone(n)) n = 113 print (calculatedigitsOfone(n)) n = 235 print (calculatedigitsOfone(n)) # This code is contributed by shiv1o43g |
C#
// C# program for the above approach using System; class GFG { static int calculatedigitsOfone( int A) { int n = A, factors = 1, count = 0, remainder = 0; while (n > 0) { int temp = factors; // check for remainders three cases mentioned in // the approach if (n % 10 == 0) { remainder = 0; } else if (n % 10 > 1) { remainder = temp; } else if (n % 10 == 1) { remainder = (A % temp) + 1; } factors *= 10; // incrementing factors for checking // different locations such as ones, // tens, hundreds places ones count += (A / factors) * temp + remainder; n = n / 10; } return count; } static void Main( string [] args) { int n = 11; Console.WriteLine(calculatedigitsOfone(n)); n = 113; Console.WriteLine(calculatedigitsOfone(n)); n = 235; Console.WriteLine(calculatedigitsOfone(n)); } } // This code is contributed by rishab |
Javascript
function calculatedigitsOfone(A) { let n = A, factors = 1, count = 0, remainder = 0; while (n > 0) { let temp = factors; // check for remainders three cases mentioned in // the approach if (n % 10 == 0) { remainder = 0; } else if (n % 10 > 1) { remainder = temp; } else if (n % 10 == 1) { remainder = (A % temp) + 1; } factors *= 10; // incrementing factors for checking // different locations such as ones, // tens, hundreds places ones count += Math.floor(A / factors) * temp + remainder; n = Math.floor(n / 10); } return count; } // Example usage let n = 11; console.log(calculatedigitsOfone(n)); n = 113; console.log(calculatedigitsOfone(n)); n = 235; console.log(calculatedigitsOfone(n)); |
4 40 154
Time complexity: O(log(n))