Count of numbers in a range that does not contain the digit M and which is divisible by M.

0 0 4 minutes read

Given three integers, the lower range L, the upper range U, and a digit M. The task is to count all the numbers between L and U such that the number is divisible by M and, also, it does not contain the digit M.

Examples:

Input: M = 9 ,L = 16 , U = 26
Output: 1
Explanation:
Within this given range ,the number that 
follows the above two given conditions is: 18.

Input: M = 6 ,L = 88 , U = 102
Output: 2
Explanation:
Within this given range ,the numbers that 
follows the above two given conditions are: 90 and 102.

Approach:

The idea is to iterate from the lower range(L) to the upper range(U) and for each number,
We will store the distinct digits of the number in a num variable and will check if the set contains the digit M or not as per the given conditions. If the number does not contain the given digit M and is divisible by M, then the counter is incremented by 1.

C++

// C++ implementation to illustrate 
// the program 
#include<bits/stdc++.h> 
using namespace std; 
 
// Function to count all the numbers 
// which does not contain the digit 'M' 
// and is divisible by M 
void contain(int L, int U, int M) 
{ 
    int count = 0; 
    for(int j = L; j < U; j++) 
    { 
         
    // Storing all the distinct 
    // digits of a number 
    set<string> num; 
    string str = to_string(j); 
    num.insert(str); 
         
    // Checking if the two conditions 
    // are satisfied or not 
    if (j % M == 0 and 
        num.find(to_string(M)) == num.end()) 
    { 
        count += 1; 
    } 
    } 
    cout << count - 2; 
} 
     
// Driver code 
int main() 
{ 
    // Lower Range 
    int L = 106; 
     
    // Upper Range 
    int U = 200; 
     
    // The digit 
    int M = 7; 
 
    contain(L, U, M); 
} 
     
// This code is contributed by BhupendraSingh 

Java

// Java implementation to illustrate 
// the program 
import java.util.*; 
 
class GFG{ 
     
// Function to count all the numbers 
// which does not contain the digit 'M' 
// and is divisible by M 
static void contain(int L, int U, int M) 
{ 
    int count = 0; 
    for(int j = L; j < U; j++) 
    { 
         
        // Storing all the distinct 
        // digits of a number 
        HashSet<String> num = new HashSet<>(); 
        String str = Integer.toString(j); 
        num.add(str); 
 
        // Checking if the two conditions 
        // are satisfied or not 
        if (j % M == 0 && !num.contains( 
            Integer.toString(M))) 
        { 
            count += 1; 
        } 
    } 
    System.out.println(count - 2); 
} 
 
// Driver code 
public static void main(String[] args) 
{ 
     
    // Lower Range 
    int L = 106; 
 
    // Upper Range 
    int U = 200; 
 
    // The digit 
    int M = 7; 
 
    contain(L, U, M); 
} 
} 
 
// This code is contributed by jrishabh99 

Python3

# Python3 implementation to illustrate 
# the program 
 
# Function to count all the numbers 
# which does not contain the digit 'M' 
# and is divisible by M 
def contain (L,U,M): 
    count = 0
    for j in range (L,U+1): 
         
        # Storing all the distinct 
        # digits of a number 
        num = set(str(j)) 
         
        # Checking if the two conditions 
        # are satisfied or not 
        if (j % M == 0 and str(M) not in num): 
            count += 1
    print (count) 
     
#Driver code 
if __name__== '__main__': 
     
    L = 106 # Lower Range 
    U = 200 # Upper Range 
    M = 7 # The digit 
 
    contain(L,U,M) 
 
# This code is contributed by parna_28 

C#

// C# implementation to illustrate
// the program
using System;
using System.Collections.Generic; 
 
class GFG{
     
// Function to count all the numbers
// which does not contain the digit 'M'
// and is divisible by M
static void contain(int L, int U, int M)
{
    int count = 0;
    for(int j = L; j < U; j++)
    {
         
        // Storing all the distinct
        // digits of a number
        HashSet<string> num = new HashSet<string>();
         
        string str = j.ToString();
        num.Add(str);
 
        // Checking if the two conditions
        // are satisfied or not
        if (j % M == 0 && !num.Contains(M.ToString())) 
        {
            count += 1;
        }
    }
    Console.Write(count - 2);
}
 
// Driver code
public static void Main(string[] args)
{
     
    // Lower Range
    int L = 106;
 
    // Upper Range
    int U = 200;
 
    // The digit
    int M = 7;
 
    contain(L, U, M);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
// Javascript implementation to illustrate
// the program
 
 
// Function to count all the numbers
// which does not contain the digit 'M'
// and is divisible by M
function contain(L, U, M)
{
    let count = 0;
    for(let j = L; j < U; j++)
    {
         
        // Storing all the distinct
        // digits of a number
        let num = new Set();
        let str = String(j);
        num.add(str);
         
        // Checking if the two conditions
        // are satisfied or not
        if (j % M == 0 && !num.has(String(M)))
        {
            count += 1;
        }
    }
    document.write(count - 2);
}
     
// Driver code
 
    // Lower Range
    let L = 106;
     
    // Upper Range
    let U = 200;
     
    // The digit
    let M = 7;
 
    contain(L, U, M);
     
// This code is contributed by _saurabh_jaiswal
</script>

Output

Time Complexity: O(U)

Auxiliary Space: O(U)

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.
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000zambiatek! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!