Given two numbers m and n, count number of m digit numbers that are divisible by n.
Examples:
Input: m = 2, n = 6
Output: 15
Explanation: Two digit numbers that are divisible by 6 are 12, 18, 24, 30, 36, ….., 96.Input: m = 3, n = 5
Output: 180
A simple solution is two try all m digit numbers. For every number, check if it is divisible by n. If yes, we increment count.
An efficient solution involves following steps.
The idea is based on the fact that starting from first divisible number, every n-th number is divisible by n.
- Find largest m digit number.
- Find largest m-1 digit number.
- Divide both number by n and subtract later from prior.
Below is the implementation of above steps.
C++
// C++ program to count m digit numbers having// n as divisor.#include<bits/stdc++.h>using namespace std;// Returns count of m digit numbers having n// as divisorint findCount(int m, int n){ // generating largest number of m digit int num1 = 0; for (int i = 0; i < m; i++) num1 = (num1 * 10) + 9; // generating largest number of m-1 digit int num2 = 0; for (int i = 0; i < (m - 1); i++) num2 = (num2 * 10) + 9; // returning number of dividend return ((num1 / n) - (num2 / n));}// Driver codeint main(){ int m = 2, n = 6; printf("%d\n", findCount(m, n)); return 0;} |
Java
// Java program to count m digit numbers having// n as divisor.class Main{ // Returns count of m digit numbers having n // as divisor static int findCount(int m, int n) { // generating largest number of m digit int num1 = 0; for (int i = 0; i < m; i++) num1 = (num1 * 10) + 9; // generating largest number of m-1 digit int num2 = 0; for (int i = 0; i < (m - 1); i++) num2 = (num2 * 10) + 9; // returning number of dividend return ((num1 / n) - (num2 / n)); } // main function public static void main (String[] args) { int m = 2, n = 6; System.out.println(findCount(m, n)); }}/* This code is contributed by Harsh Agarwal */ |
Python3
# Python3 program to count m digit# numbers having n as divisor.# Returns count of m digit # numbers having n as divisordef findCount(m, n): # Generating largest number of m digit num1 = 0 for i in range(0, m): num1 = (num1 * 10) + 9 # Generating largest number of m-1 digit num2 = 0 for i in range(0, (m - 1)): num2 = (num2 * 10) + 9 # returning number of dividend return int((num1 / n) - (num2 / n)) # Driver codem = 2; n = 6print(findCount(m, n)) # This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to count m digit numbers// having n as divisor.using System; class GfG { // Returns count of m digit numbers // having n as divisor static int findCount(int m, int n) { // generating largest number // of m digit int num1 = 0; for (int i = 0; i < m; i++) num1 = (num1 * 10) + 9; // generating largest number // of m-1 digit int num2 = 0; for (int i = 0; i < (m - 1); i++) num2 = (num2 * 10) + 9; // returning number of dividend return ((num1 / n) - (num2 / n)); } // main function public static void Main () { int m = 2, n = 6; Console.Write(findCount(m, n)); }}// This code is contributed by parashar. |
PHP
<?php// PHP program to count m digit// numbers having n as divisor.// Returns count of m digit numbers// having n as divisorfunction findCount($m, $n){ // generating largest number // of m digit $num1 = 0; for ($i = 0; $i < $m; $i++) $num1 = ($num1 * 10) + 9; // generating largest number // of m-1 digit $num2 = 0; for ($i = 0; $i < ($m - 1); $i++) $num2 = ($num2 * 10) + 9; // returning number of dividend return (($num1 / $n) - ($num2 / $n));}// Driver code$m = 2; $n = 6;echo findCount($m, $n), "\n";// This code is contributed by ajit?> |
Javascript
<script>// Javascript program to count m digit// numbers having n as divisor.// Returns count of m digit numbers// having n as divisorfunction findCount(m, n){ // generating largest number // of m digit let num1 = 0; for (let i = 0; i < m; i++) num1 = (num1 * 10) + 9; // generating largest number // of m-1 digit let num2 = 0; for (let i = 0; i < (m - 1); i++) num2 = (num2 * 10) + 9; // returning number of dividend return ((num1 / n) - (num2 / n));}// Driver codelet m = 2; n = 6;document.write(findCount(m, n) + "<br>");// This code is contributed by gfgking</script> |
Output :
15
Time complexity: O(m)
Auxiliary space: O(1) as it is using constant space for variables
This article is contributed by Aditya Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. 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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
