Given three integers N, A and B, the task is to find whether N is divisible by any number that contains only A and B as it’s digits.
Examples:
Input: N = 106, a = 3, b = 5
Output: Yes
106 is divisible by 53Input: N = 107, a = 3, b = 5
Output: No
Approach 1 (Recursive):
An efficient solution is to make all the numbers that contains a and b as their digits using recursive function starting with the numbers a and b. If function call is fun(x) then recursively call for fun(x * 10 + a) and fun(x * 10 + b). If n is divisible by any of the number then print Yes else print No.
Below is the implementation of the above approach:
C++
// C++ program to find if number N is divisible by a// number that contains only a and b as it's digits#include <bits/stdc++.h>using namespace std;// Function to check whether n is divisible // by a number whose digits are either a or bbool isDivisibleRec(int x, int a, int b, int n){ // base condition if (x > n) return false; if (n % x == 0) return true; // recursive call return (isDivisibleRec(x * 10 + a, a, b, n) || isDivisibleRec(x * 10 + b, a, b, n));}bool isDivisible(int a, int b, int n){ // Check for all numbers beginning with 'a' or 'b' return isDivisibleRec(a, a, b, n) || isDivisibleRec(b, a, b, n);}// Driver programint main(){ int a = 3, b = 5, n = 53; if (isDivisible(a, b, n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program to find if number N is divisible by a// number that contains only a and b as it's digitsimport java.util.*;class solution{// Function to check whether n is divisible // by a number whose digits are either a or bstatic boolean isDivisibleRec(int x, int a, int b, int n){ // base condition if (x > n) return false; if (n % x == 0) return true; // recursive call return (isDivisibleRec(x * 10 + a, a, b, n) || isDivisibleRec(x * 10 + b, a, b, n));}static boolean isDivisible(int a, int b, int n){// Check for all numbers beginning with 'a' or 'b'return isDivisibleRec(a, a, b, n) ||isDivisibleRec(b, a, b, n);}// Driver programpublic static void main(String args[]){ int a = 3, b = 5, n = 53; if (isDivisible(a, b, n)) System.out.print("Yes"); else System.out.print("No");}}//contributed by Arnab Kundu |
Python3
# Python 3 program to find if number N # is divisible by a number that contains # only a and b as it's digits# Function to check whether n is divisible # by a number whose digits are either a or bdef isDivisibleRec(x, a, b, n): # base condition if (x > n): return False if (n % x == 0): return True # recursive call return (isDivisibleRec(x * 10 + a, a, b, n) or isDivisibleRec(x * 10 + b, a, b, n))def isDivisible(a, b, n): # Check for all numbers beginning # with 'a' or 'b' return (isDivisibleRec(a, a, b, n) or isDivisibleRec(b, a, b, n))# Driver Codea = 3; b = 5; n = 53;if (isDivisible(a, b, n)): print("Yes")else: print("No")# This code is contributed # by Akanksha Rai |
C#
// C# program to find if number N is // divisible by a number that contains// only a and b as it's digits using System;class GFG{ // Function to check whether n is divisible // by a number whose digits are either a or b static bool isDivisibleRec(int x, int a, int b, int n) { // base condition if (x > n) return false; if (n % x == 0) return true; // recursive call return (isDivisibleRec(x * 10 + a, a, b, n) || isDivisibleRec(x * 10 + b, a, b, n)); } static bool isDivisible(int a, int b, int n) { // Check for all numbers beginning// with 'a' or 'b' return isDivisibleRec(a, a, b, n) || isDivisibleRec(b, a, b, n); } // Driver Codestatic public void Main (){ int a = 3, b = 5, n = 53; if (isDivisible(a, b, n)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed by Sachin |
PHP
<?php// PHP program to find if number N is// divisible by a number that contains// only a and b as it's digits// Function to check whether n is divisible // by a number whose digits are either a or bfunction isDivisibleRec($x, $a, $b, $n){ // base condition if ($x > $n) return false; if ($n % $x == 0) return true; // recursive call return (isDivisibleRec($x * 10 + $a, $a, $b, $n) || isDivisibleRec($x * 10 + $b, $a, $b, $n));}function isDivisible($a, $b, $n){ // Check for all numbers beginning // with 'a' or 'b'return isDivisibleRec($a, $a, $b, $n) || isDivisibleRec($b, $a, $b, $n);}// Driver Code$a = 3; $b = 5; $n = 53;if (isDivisible($a, $b, $n)) echo "Yes";else echo "No";// This code is contributed// by Akanksha Rai |
Javascript
<script>// Javascript program to find if number// N is divisible by a number that // contains only a and b as it's digits// Function to check whether n is divisible // by a number whose digits are either a or bfunction isDivisibleRec(x, a, b, n){ // Base condition if (x > n) return false; if (n % x == 0) return true; // Recursive call return(isDivisibleRec(x * 10 + a, a, b, n) || isDivisibleRec(x * 10 + b, a, b, n));}function isDivisible(a, b, n){ // Check for all numbers beginning // with 'a' or 'b' return isDivisibleRec(a, a, b, n) || isDivisibleRec(b, a, b, n);}// Driver codelet a = 3, b = 5, n = 53;if (isDivisible(a, b, n)) document.write("Yes");else document.write("No"); // This code is contributed by souravmahato348</script> |
Output
Yes
Approach 2 (Queue Based):
The idea is to generate all numbers (smaller than n) containing digits a and b. For every number check if it divides n or not. How to generate all numbers smaller than n? We use queue for this. Initially we push ‘a’ and ‘b’ to the queue. Then we run a loop while front of queue is smaller than n. We pop an item one by one and for ever popped item x, we generate next numbers x*10 + a and x*10 + b and enqueue them. Time complexity of this approach is O(n).
Please refer below post for implementation of this approach.
Count of Binary Digit numbers smaller than N
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!
