Count of Integers in given range consisting only given set of Digits
Given two integers L and R, and an array arr[] containing single digit integers, the task is to find all the integers in the range [L, R) consisting of digits from given array of digits.
Examples:
Input: L = 1, R = 100, arr[] = {2, 3, 5, 7}
Output: 20
Explanation: The number between 1 and 100 total integers which are made up with 2, 3, 5, 7 are:
2, 3, 5, 7, 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75, and 77. Total 20.Input: L = 50, R = 60, arr[] = 5
Output: 1
Explanation: The only number in range 50 and 60 55.
Approach: The solution to the problem is based on greedy approach by using the below idea:
Traverse each integer in range [L, R) and check if it consists of only given set of digits.
Follow the steps below to solve the problem:
- Iterate over the range [L, R).
- Check whether the number is a combination of numbers given in arr[] or not with the help of a set.
- If it is a subset of given digits then increase count by 1, otherwise not.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function Check number is // subset of prime digit of not bool has_val( int x, set< int >& st) { while (x != 0) { if (st.find(x % 10) == st.end()) return false ; x /= 10; } return true ; } // Function to find // non-prime between range int total_Num( int A, int B, int arr[], int N) { int ans = 0; set< int > st; for ( int i = 0; i < N; i++) st.insert(arr[i]); // Loop to check if number contains // only the digits in given set for ( int k = A; k < B; k++) { if (has_val(k, st)) ans += 1; } return ans; } // Driver Code int main() { int L = 1, R = 100; int arr[] = { 2, 3, 5, 7 }; int N = sizeof (arr) / sizeof (arr[0]); int ans = total_Num(L, R, arr, N); cout << ans; return 0; } |
Java
// Java code to implement the approach import java.util.*; public class GFG { // Function Check number is // subset of prime digit of not static boolean has_val( int x, HashSet<Integer> st) { while (x != 0 ) { if (st.contains(x % 10 ) == false ) return false ; x /= 10 ; } return true ; } // Function to find // non-prime between range static int total_Num( int A, int B, int arr[], int N) { int ans = 0 ; HashSet<Integer> st = new HashSet<>(); for ( int i = 0 ; i < N; i++) st.add(arr[i]); // Loop to check if number contains // only the digits in given set for ( int k = A; k < B; k++) { if (has_val(k, st)) ans += 1 ; } return ans; } // Driver Code public static void main(String args[]) { int L = 1 , R = 100 ; int [] arr = { 2 , 3 , 5 , 7 }; int N = arr.length; int ans = total_Num(L, R, arr, N); System.out.print(ans); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# python3 code to implement the approach # Function Check number is # subset of prime digit of not def has_val(x, st): while (x ! = 0 ): if ( not x % 10 in st): return False x / / = 10 return True # Function to find # non-prime between range def total_Num(A, B, arr, N): ans = 0 st = set () for i in range ( 0 , N): st.add(arr[i]) # Loop to check if number contains # only the digits in given set for k in range (A, B): if (has_val(k, st)): ans + = 1 return ans # Driver Code if __name__ = = "__main__" : L, R = 1 , 100 arr = [ 2 , 3 , 5 , 7 ] N = len (arr) ans = total_Num(L, R, arr, N) print (ans) # This code is contributed by rakeshsahni |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG{ // Function Check number is // subset of prime digit of not static bool has_val( int x, HashSet< int > st) { while (x != 0) { if (st.Contains(x % 10) == false ) return false ; x /= 10; } return true ; } // Function to find // non-prime between range static int total_Num( int A, int B, int [] arr, int N) { int ans = 0; HashSet< int > st = new HashSet< int >(); for ( int i = 0; i < N; i++) st.Add(arr[i]); // Loop to check if number contains // only the digits in given set for ( int k = A; k < B; k++) { if (has_val(k, st)) ans += 1; } return ans; } // Driver Code static public void Main (){ int L = 1, R = 100; int [] arr = { 2, 3, 5, 7 }; int N = arr.Length; int ans = total_Num(L, R, arr, N); Console.Write(ans); } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code for the above approach // Function Check number is // subset of prime digit of not function has_val(x, st) { while (x != 0) { if (!st.has(x % 10)) return false ; x = Math.floor(x / 10); } return true ; } // Function to find // non-prime between range function total_Num(A, B, arr, N) { let ans = 0; let st = new Set(); for (let i = 0; i < N; i++) st.add(arr[i]); // Loop to check if number contains // only the digits in given set for (let k = A; k < B; k++) { if (has_val(k, st)) ans += 1; } return ans; } // Driver Code let L = 1, R = 100; let arr = [2, 3, 5, 7]; let N = arr.length; let ans = total_Num(L, R, arr, N); document.write(ans); // This code is contributed by Potta Lokesh </script> |
20
Time Complexity: O((R-L)*logN)
Auxiliary Space: O(1)
Contact Us