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 = 15print(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)
If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.uk or mail your article to review-team@neveropen.co.uk. See your article appearing on the neveropen main page and help other Geeks.
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!
