Count divisors of n that have at-least one digit common with n
Given a number n, find the number of divisors whose at least one digit in the decimal representation matches with the number n.
Examples:
Input : n = 10 Output: 2 Explanation: numbers are 1 and 10, 1 and 10 both have a nimbus of 1 digit common with n = 10. Input : n = 15 Output: 3 Explanation: the numbers are 1, 5, 15, all of them have a minimum of 1 digit common.
A naive approach is to iterate from 1 to n and check for all the divisors and use hashing to determine if any of the digits match with n or not.
Time complexity: O(n)
Auxiliary space: O(1)
An efficient approach is to iterate from 1 to sqrt(n) and check for all the divisors i and n/i, if both are different, we check if there is any match for i and n/i, if yes we simply add 1 to the answer. We use hashing to store if a number is present or not.
Below is the implementation of the above approach
C++
// C++ program to count divisors of n that have at least // one digit common with n #include <bits/stdc++.h> using namespace std; // function to return true if any digit of m is // present in hash[]. bool isDigitPresent( int m, bool hash[]) { // check till last digit while (m) { // if number is also present in original number // then return true if (hash[m % 10]) return true ; m = m / 10; } // if no number matches then return 1 return false ; } // Count the no of divisors that have at least 1 digits // same int countDivisibles( int n) { // Store digits present in n in a hash[] bool hash[10] = { 0 }; int m = n; while (m) { // marks that the number is present hash[m % 10] = true ; // last digit removed m = m / 10; } // loop to traverse from 1 to sqrt(n) to // count divisors int ans = 0; for ( int i = 1; i <= sqrt (n); i++) { // if i is the factor if (n % i == 0) { // call the function to check if any // digits match or not if (isDigitPresent(i, hash)) ans++; if (n / i != i) { // if n/i != i then a different number, // then check it also if (isDigitPresent(n/i, hash)) ans++; } } } // return the answer return ans; } // driver program to test the above function int main() { int n = 15; cout << countDivisibles(n); return 0; } |
Java
// Java program to count divisors of n that // have at least one digit common with n import java.io.*; public class GFG { // function to return true if any digit // of m is present in hash[]. static boolean isDigitPresent( int m, boolean hash[]) { // check till last digit while (m > 0 ) { // if number is also present // in original number then // return true if (hash[m % 10 ]) return true ; m = m / 10 ; } // if no number matches then // return 1 return false ; } // Count the no of divisors that // have at least 1 digits same static int countDivisibles( int n) { // Store digits present in n // in a hash[] boolean hash[] = new boolean [ 10 ]; int m = n; while (m > 0 ) { // marks that the number // is present hash[m % 10 ] = true ; // last digit removed m = m / 10 ; } // loop to traverse from 1 to // sqrt(n) to count divisors int ans = 0 ; for ( int i = 1 ; i <= Math.sqrt(n); i++) { // if i is the factor if (n % i == 0 ) { // call the function to // check if any digits // match or not if (isDigitPresent(i, hash)) ans++; if (n / i != i) { // if n/i != i then a // different number, // then check it also if (isDigitPresent(n/i, hash)) ans++; } } } // return the answer return ans; } //driver code public static void main (String[] args) { int n = 15 ; System.out.print(countDivisibles(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to count divisors # of n that have at least # one digit common with n import math # Function to return true if any # digit of m is present in hash[]. def isDigitPresent(m, Hash ): # check till last digit while (m): # if number is also present in original # number then return true if ( Hash [m % 10 ]): return True m = m / / 10 # if no number matches then return 1 return False # Count the no of divisors that # have at least 1 digits same def countDivisibles(n): # Store digits present in n in a hash[] Hash = [ False for i in range ( 10 )] m = n while (m): # marks that the number is present Hash [m % 10 ] = True # last digit removed m = m / / 10 # loop to traverse from 1 to sqrt(n) to # count divisors ans = 0 for i in range ( 1 , int (math.sqrt(n)) + 1 ): # if i is the factor if (n % i = = 0 ): # call the function to check if any # digits match or not if (isDigitPresent(i, Hash )): ans + = 1 if (n / / i ! = i): # if n/i != i then a different number, # then check it also if (isDigitPresent(n / / i, Hash )): ans + = 1 # return the answer return ans # Driver Code n = 15 print (countDivisibles(n)) # This code is contributed by Anant Agarwal. |
C#
// Program to count divisors of // n that have at least one digit // common with n using System; class GFG { // function to return true if // any digit of m is present // in hash[]. static bool isDigitPresent( int m, bool [] hash) { // check till last digit while (m > 0) { // if number is also present in the // original number then return true if (hash[m % 10]) return true ; m = m / 10; } // if no number matches then return 1 return false ; } // Count the no of divisors that have // at least 1 digits same static int countDivisibles( int n) { // Store digits present in n in a hash[] bool [] hash = new bool [10]; int m = n; while (m > 0) { // marks that the number is present hash[m % 10] = true ; // last digit removed m = m / 10; } // loop to traverse from 1 to sqrt(n) to // count divisors int ans = 0; for ( int i = 1; i <= Math.Sqrt(n); i++) { // if i is the factor if (n % i == 0) { // call the function to check if any // digits match or not if (isDigitPresent(i, hash)) ans++; if (n / i != i) { // if n/i != i then a different number, // then check it also if (isDigitPresent(n / i, hash)) ans++; } } } // return the answer return ans; } // Driver code public static void Main() { int n = 15; Console.Write(countDivisibles(n)); } } // This code is contributed by Anant Agarwal. |
PHP
<?php // PHP program to count divisors // of n that have at least // one digit common with n // function to return true // if any digit of m is // present in hash[]. function isDigitPresent( $m , $hash ) { // check till last digit while ( $m ) { // if number is also // present in original // number then return true if ( $hash [ $m % 10]) return true; $m = (int)( $m / 10); } // if no number matches // then return 1 return false; } // Count the no of divisors // that have at least 1 digits // same function countDivisibles( $n ) { // Store digits present // in n in a hash[] $hash = array_fill (0, 10, false); $m = $n ; while ( $m ) { // marks that the // number is present $hash [ $m % 10] = true; // last digit removed $m = (int)( $m / 10); } // loop to traverse from // 1 to sqrt(n) to count divisors $ans = 0; for ( $i = 1; $i <= sqrt( $n ); $i ++) { // if i is the factor if ( $n % $i == 0) { // call the function // to check if any // digits match or not if (isDigitPresent( $i , $hash )) $ans ++; if ((int)( $n / $i ) != $i ) { // if n/i != i then a // different number, // then check it also if (isDigitPresent((int)( $n / $i ), $hash )) $ans ++; } } } // return the answer return $ans ; } // Driver code $n = 15; echo countDivisibles( $n ); // This code is contributed by mits ?> |
Javascript
<script> // JavaScript program to count divisors of n that // have at least one digit common with n // function to return true if any digit // of m is present in hash[]. function isDigitPresent(m, hash) { // check till last digit while (m > 0) { // if number is also present // in original number then // return true if (hash[m % 10]) return true ; m = Math.floor(m / 10); } // if no number matches then // return 1 return false ; } // Count the no of divisors that // have at least 1 digits same function countDivisibles(n) { // Store digits present in n // in a hash[] let hash = Array.from({length: 10}, (_, i) => 0); let m = n; while (m > 0) { // marks that the number // is present hash[m % 10] = true ; // last digit removed m = Math.floor(m / 10); } // loop to traverse from 1 to // sqrt(n) to count divisors let ans = 0; for (let i = 1; i <= Math.sqrt(n); i++) { // if i is the factor if (n % i == 0) { // call the function to // check if any digits // match or not if (isDigitPresent(i, hash)) ans++; if (n / i != i) { // if n/i != i then a // different number, // then check it also if (isDigitPresent(n/i, hash)) ans++; } } } // return the answer return ans; } // Driver Code let n = 15; document.write(countDivisibles(n)); </script> |
Output
3
Time complexity: O(sqrt n)
Auxiliary Space: O(1)