Given a number N which may be 10^5 digits long, the task is to count all the digits in N which divide N. Divisibility by 0 is not allowed. If any digit in N which is repeated divides N, then all repetitions of that digit should be counted i. e., N = 122324, here 2 divides N and it appears 3 times. So count for digit 2 will be 3.
Examples:
Input : N = "35"
Output : 1
There are two digits in N and 1 of them
(5)divides it.
Input : N = "122324"
Output : 5
N is divisible by 1, 2 and 4
Recommended Practice
Count Digits
Try It!
How to check divisibility of a digit for large N stored as string?
The idea is to use distributive property of mod operation.
(x+y)%a = ((x%a) + (y%a)) % a.
// This function returns true if digit divides N,
// else false
bool divisible(string N, int digit)
{
int ans = 0;
for (int i = 0; i < N.length(); i++)
{
// (N[i]-'0') gives the digit value and
// form the number
ans = (ans*10 + (N[i]-'0'));
// We use distributive property of mod here.
ans %= digit;
}
return (ans == 0);
}
A simple solution for this problem is to read number in string form and one by one check divisibility by each digit which appears in N. Time complexity for this approach will be O(N2).
An efficient solution for this problem is to use an extra array divide[] of size 10. Since we have only 10 digits so run a loop from 1 to 9 and check divisibility of N with each digit from 1 to 9. If any digit divides N then mark true in divide[] array at digit as index. Now traverse the number string and increment result if divide[i] is true for current digit i.
C++
#include<bits/stdc++.h>
using namespace std;
bool divisible(string N, int digit)
{
int ans = 0;
for ( int i = 0; i < N.length(); i++)
{
ans = (ans*10 + (N[i]- '0' ));
ans %= digit;
}
return (ans == 0);
}
int allDigits(string N)
{
bool divide[10] = { false };
divide[1] = true ;
for ( int digit=2; digit<=9; digit++)
{
if (divisible(N, digit))
divide[digit] = true ;
}
int result = 0;
for ( int i=0; i<N.length(); i++)
{
if (divide[N[i]- '0' ] == true )
result++;
}
return result;
}
int main()
{
string N = "122324" ;
cout << allDigits(N);
return 0;
}
|
Java
import java.util.*;
class solution
{
static boolean divisible(String N, int digit)
{
int ans = 0 ;
for ( int i = 0 ; i < N.length(); i++)
{
ans = (ans* 10 + (N.charAt(i)- '0' ));
ans %= digit;
}
return (ans == 0 );
}
static int allDigits(String N)
{
Boolean[] divide = new Boolean[ 10 ];
Arrays.fill(divide, Boolean.FALSE);
divide[ 1 ] = true ;
for ( int digit= 2 ; digit<= 9 ; digit++)
{
if (divisible(N, digit))
divide[digit] = true ;
}
int result = 0 ;
for ( int i= 0 ; i<N.length(); i++)
{
if (divide[N.charAt(i)- '0' ] == true )
result++;
}
return result;
}
public static void main(String args[])
{
String N = "122324" ;
System.out.println(allDigits(N));
}
}
|
Python3
def divisible(N, digit):
ans = 0 ;
for i in range ( len (N)):
ans = (ans * 10 + ( ord (N[i]) - ord ( '0' )));
ans % = digit;
return (ans = = 0 );
def allDigits(N):
divide = [ False ] * 10 ;
divide[ 1 ] = True ;
for digit in range ( 2 , 10 ):
if (divisible(N, digit)):
divide[digit] = True ;
result = 0 ;
for i in range ( len (N)):
if (divide[( ord (N[i]) - ord ( '0' ))] = = True ):
result + = 1 ;
return result;
N = "122324" ;
print (allDigits(N));
|
C#
using System;
class GFG {
static bool divisible( string N, int digit)
{
int ans = 0;
for ( int i = 0; i < N.Length; i++)
{
ans = (ans * 10 + (N[i] - '0' ));
ans %= digit;
}
return (ans == 0);
}
static int allDigits( string N)
{
bool [] divide = new bool [10];
for ( int i = 0; i < divide.Length; i++)
{
divide[i] = false ;
}
divide[1] = true ;
for ( int digit = 2; digit <= 9; digit++)
{
if (divisible(N, digit))
divide[digit] = true ;
}
int result = 0;
for ( int i = 0; i < N.Length; i++)
{
if (divide[N[i] - '0' ] == true )
result++;
}
return result;
}
public static void Main()
{
string N = "122324" ;
Console.Write(allDigits(N));
}
}
|
Javascript
<script>
function divisible(N, digit)
{
let ans = 0;
for (let i = 0; i < N.length; i++)
{
ans = (ans * 10 + (N[i] - '0' ));
ans %= digit;
}
return (ans == 0);
}
function allDigits(N)
{
let divide = [];
for (let i = 0; i < divide.length; i++)
{
divide[i] = false ;
}
divide[1] = true ;
for (let digit = 2; digit <= 9; digit++)
{
if (divisible(N, digit))
divide[digit] = true ;
}
let result = 0;
for (let i = 0; i < N.length; i++)
{
if (divide[N[i] - '0' ] == true )
result++;
}
return result;
}
let N = "122324" ;
document.write(allDigits(N));
</script>
|
PHP
<?php
function divisible( $N , $digit )
{
$ans = 0;
for ( $i = 0; $i < strlen ( $N ); $i ++)
{
$ans = ( $ans * 10 + (int)( $N [ $i ] - '0' ));
$ans %= $digit ;
}
return ( $ans == 0);
}
function allDigits( $N )
{
$divide = array_fill (0, 10, false);
$divide [1] = true;
for ( $digit = 2; $digit <= 9; $digit ++)
{
if (divisible( $N , $digit ))
$divide [ $digit ] = true;
}
$result = 0;
for ( $i = 0; $i < strlen ( $N ); $i ++)
{
if ( $divide [(int)( $N [ $i ] - '0' )] == true)
$result ++;
}
return $result ;
}
$N = "122324" ;
echo allDigits( $N );
?>
|
Time Complexity: O(n)
Auxiliary space: O(1)
This article is contributed by Shashank Mishra .
Approach#2:Using reursion
In this approach, we will use recursion to count the number of digits that divide N. We will first check if the length of N is 1. If it is, we will check if the digit divides N. If it does, we will return 1, else we will return 0. If the length of N is greater than 1, we will call the function recursively on the first digit of N and add the result to the recursive call on the remaining digits of N.
Algorithm
1. Take the input value of N.
2. Define a recursive function to count the number of digits that divide N.
3. If the length of N is 1, check if the digit divides N. If it does, return 1, else return 0.
4. If the length of N is greater than 1, call the function recursively on the first digit of N and add the result to the recursive call on the remaining digits of N.
5. Return the result of the recursive call.
C++
#include <iostream>
#include <string>
using namespace std;
int helper(string N) {
if (N.length() == 1) {
if (N != "0" && N != "1" && stoi(N) % stoi(N) == 0) {
return 1;
} else {
return 0;
}
} else {
if (N[0] != '0' && N[0] != '1' && stoi(N) % stoi(string(1, N[0])) == 0) {
return 1 + helper(N.substr(1));
} else {
return helper(N.substr(1));
}
}
}
int count_dividing_digits(string N)
{
return helper(N);
}
int main() {
string N = "122324" ;
cout << count_dividing_digits(N) << endl;
return 0;
}
|
Java
public class Main {
static int helper(String N) {
if (N.length() == 1 ) {
if (!N.equals( "0" ) && !N.equals( "1" ) && Integer.parseInt(N) % Integer.parseInt(N) == 0 ) {
return 1 ;
} else {
return 0 ;
}
} else {
if (N.charAt( 0 ) != '0' && N.charAt( 0 ) != '1' && Integer.parseInt(N) % Integer.parseInt(String.valueOf(N.charAt( 0 ))) == 0 ) {
return 1 + helper(N.substring( 1 ));
} else {
return helper(N.substring( 1 ));
}
}
}
static int countDividingDigits(String N) {
return helper(N);
}
public static void main(String[] args) {
String N = "122324" ;
System.out.println(countDividingDigits(N));
}
}
|
Python3
def count_dividing_digits(N):
def helper(N):
if len (N) = = 1 :
if int (N) ! = 0 and int (N) ! = 1 and int (N) % int (N) = = 0 :
return 1
else :
return 0
else :
if int (N[ 0 ]) ! = 0 and int (N[ 0 ]) ! = 1 and int (N) % int (N[ 0 ]) = = 0 :
return 1 + helper(N[ 1 :])
else :
return helper(N[ 1 :])
return helper( str (N))
N = "122324"
print (count_dividing_digits(N))
|
C#
using System;
class Program
{
static int Helper( string N)
{
if (N.Length == 1)
{
if (N != "0" && N != "1" && int .Parse(N) % int .Parse(N) == 0)
{
return 1;
}
else
{
return 0;
}
}
else
{
if (N[0] != '0' && N[0] != '1' && int .Parse(N) % int .Parse(N[0].ToString()) == 0)
{
return 1 + Helper(N.Substring(1));
}
else
{
return Helper(N.Substring(1));
}
}
}
static int CountDividingDigits( string N)
{
return Helper(N);
}
static void Main()
{
string N = "122324" ;
Console.WriteLine(CountDividingDigits(N));
}
}
|
Javascript
function helper(N) {
if (N.length === 1) {
if (N !== '0' && N !== '1' && parseInt(N) % parseInt(N) === 0) {
return 1;
} else {
return 0;
}
} else {
if (N[0] !== '0' && N[0] !== '1' && parseInt(N) % parseInt(N[0]) === 0) {
return 1 + helper(N.substr(1));
} else {
return helper(N.substr(1));
}
}
}
function countDividingDigits(N) {
return helper(N);
}
function main() {
const N = "122324" ;
console.log(countDividingDigits(N));
}
main();
|
Time complexity: O(n), where n is the number of digits in N. This is because the code iterates through each digit of N exactly once and performs constant time operations on each digit.
Auxiliary Space: O(n), since the recursive function helper() is called n times and each call creates a new stack frame with some constant amount of memory usage. Therefore, the space used by the function scales linearly with the input size.
In this approach, we create a vector counts of size 10 to keep track of the number of times each digit 0-9 appears and divides the input string N. We loop through each character in the input string N, convert it to an integer, and check if it is a divisor of N. If so, we increment the count for that digit. Finally, we loop through the counts vector and add up the counts for all digits except 0 (since 0 cannot be a divisor of any number except 0 itself).
- Initialize a vector counts of size 10 with all elements set to zero.
- Loop through each character in the input string N.
- Convert the character to an integer value.
- Check if the integer value is zero. If it is, continue to the next iteration of the loop.
- Check if the integer value is a divisor of N. If it is, increment the count of the corresponding digit in the counts vector.
- Loop through the counts vector and add up the counts for all digits except 0.
- Return the total count.
C++
#include <iostream>
#include <vector>
using namespace std;
int allDigits(string N) {
vector< int > counts(10, 0);
for ( char ch : N) {
int digit = ch - '0' ;
if (digit == 0) continue ;
if (stoi(N) % digit == 0) counts[digit]++;
}
int result = 0;
for ( int i = 1; i < 10; i++) {
if (counts[i] > 0) result += counts[i];
}
return result;
}
int main() {
string N = "122324" ;
cout << allDigits(N) << endl;
return 0;
}
|
Java
import java.util.Arrays;
public class AllDigits {
public static int allDigits(String N) {
int [] counts = new int [ 10 ];
for ( char ch : N.toCharArray()) {
int digit = ch - '0' ;
if (digit == 0 ) continue ;
if (Integer.parseInt(N) % digit == 0 ) counts[digit]++;
}
int result = 0 ;
for ( int i = 1 ; i < 10 ; i++) {
if (counts[i] > 0 ) result += counts[i];
}
return result;
}
public static void main(String[] args) {
String N = "122324" ;
System.out.println(allDigits(N));
}
}
|
Python3
def all_digits(N):
counts = [ 0 ] * 10
for ch in N:
digit = int (ch)
if digit = = 0 :
continue
if int (N) % digit = = 0 :
counts[digit] + = 1
result = 0
for i in range ( 1 , 10 ):
if counts[i] > 0 :
result + = counts[i]
return result
N = "122324"
print (all_digits(N))
|
C#
using System;
using System.Collections.Generic;
class Program {
static int AllDigits( string N)
{
int [] counts = new int [10];
foreach ( char ch in N)
{
int digit = ch - '0' ;
if (digit == 0)
continue ;
if ( int .Parse(N) % digit == 0)
counts[digit]++;
}
int result = 0;
for ( int i = 1; i < 10; i++) {
if (counts[i] > 0)
result += counts[i];
}
return result;
}
static void Main()
{
string N = "122324" ;
Console.WriteLine(AllDigits(N));
}
}
|
Javascript
function allDigits(N) {
const counts = Array(10).fill(0);
for (const ch of N) {
const digit = parseInt(ch);
if (digit === 0) continue ;
if (parseInt(N) % digit === 0) counts[digit]++;
}
let result = 0;
for (let i = 1; i < 10; i++) {
if (counts[i] > 0) result += counts[i];
}
return result;
}
const N = "122324" ;
console.log(allDigits(N));
|
Contact Us