Given an integer K and an array Q[][] consisting of N queries of type {L, R}, the task for each query is to print the count of numbers from the range [L, R] that doesn’t contain the digit K in their decimal representation or octal representation.
Examples:
Input: K = 7, Q[][] = {{1, 15}}
Output: 13
Explanation:
Only number 7 and 15 contains digit K in its octal or decimal representations.
Octal representation of number 7 is 7.
Octal representation of number 15 is 17.Input: K = 8, Q[][] = {{1, 10}}
Output: 9
Explanation:
Only number 8 contains digit K in its decimal representations.
Octal representation of number 8 is 10.
Naive Approach: The idea is to traverse the range [L, R] for each query and find those numbers whose decimal and octal representations does not contain the digit K. Print the count of such numbers.
Time Complexity: O(N2*(log10(N) + log8(N)))
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to pre-compute the count of all such numbers using Prefix Sum technique. Follow the steps below to solve the problem:
- Initialize an array, say pref[], to store the count of numbers in the range [0, i] that contains digit K in their octal or decimal representation.
- Now traverse the range [0, 1e6] and perform the following steps:
- If the number contains digit K in either octal representation or decimal representation, then update pref[i] as pref[i – 1] + 1.
- Otherwise, update pref[i] as pref[i – 1].
- Traverse the given queries and print the count for each query as
Q[i][1] – Q[i][0] + 1 – (pref[Q[i][1]] – pref[Q[i][0] – 1])
Below is the implementation for the above approach :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the given digit// 'K' is present in the decimal and octal// representations of num or notbool contains(int num, int K, int base){ // Stores if the digit exists // or not bool isThere = 0; // Iterate till nums is non-zero while (num) { // Find the remainder int remainder = num % base; // If the remainder is K if (remainder == K) { isThere = 1; } num /= base; } return isThere;}// Function to count the numbers in the// range [1, N] such that it doesn't// contain the digit 'K' in its decimal// and octal representationvoid count(int n, int k, vector<vector<int> > v){ // Stores count of numbers in the // range [0, i] that contains the // digit 'K' in its octal or // decimal representation int pref[1000005] = { 0 }; // Traverse the range [0, 1e6 + 5] for (int i = 1; i < 1e6 + 5; i++) { // Check if i contains the digit // 'K' in its decimal or // octal representation bool present = contains(i, k, 10) || contains(i, k, 8); // Update pref[i] pref[i] += pref[i - 1] + present; } // Print the answer of queries for (int i = 0; i < n; ++i) { cout << v[i][1] - v[i][0] + 1 - (pref[v[i][1]] - pref[v[i][0] - 1]) << ' '; }}// Driver Codeint main(){ int K = 7; vector<vector<int> > Q = { { 2, 5 }, { 1, 15 } }; int N = Q.size(); // Function Call count(N, K, Q);} |
Java
// Java program for the above approachimport java.util.*;public class GFG{ // Function to check if the given digit // 'K' is present in the decimal and octal // representations of num or not static boolean contains(int num, int K, int Base) { // Stores if the digit exists // or not boolean isThere = false; // Iterate till nums is non-zero while (num > 0) { // Find the remainder int remainder = num % Base; // If the remainder is K if (remainder == K) { isThere = true; } num /= Base; } return isThere; } // Function to count the numbers in the // range [1, N] such that it doesn't // contain the digit 'K' in its decimal // and octal representation static void count(int n, int k, Vector<Vector<Integer> > v) { // Stores count of numbers in the // range [0, i] that contains the // digit 'K' in its octal or // decimal representation int[] pref = new int[1000005]; // Traverse the range [0, 1e6 + 5] for (int i = 1; i < 1e6 + 5; i++) { // Check if i contains the digit // 'K' in its decimal or // octal representation boolean present = contains(i, k, 10) || contains(i, k, 8); // Update pref[i] if(present) { pref[i] += pref[i - 1] + 1; } } // Print the answer of queries System.out.print((v.get(0).get(1) - v.get(0).get(0) + 1 - (pref[v.get(0).get(1)] - pref[v.get(0).get(0) - 1])) + " "); System.out.print((v.get(1).get(1) - v.get(1).get(0) - (pref[v.get(1).get(1)] - pref[v.get(1).get(0) - 1])) + " "); } // Driver code public static void main(String[] args) { int K = 7; Vector<Vector<Integer> > Q = new Vector<Vector<Integer> >(); Q.add(new Vector<Integer>()); Q.get(0).add(2); Q.get(0).add(5); Q.add(new Vector<Integer>()); Q.get(1).add(1); Q.get(1).add(15); int N = Q.size(); // Function Call count(N, K, Q); }}// This code is contributed by divyeshrabadiya07. |
Python3
# Python3 program for the above approach# Function to check if the given digit# 'K' is present in the decimal and octal# representations of num or notdef contains(num, K, base): # Stores if the digit exists # or not isThere = 0 # Iterate till nums is non-zero while (num): # Find the remainder remainder = num % base # If the remainder is K if (remainder == K): isThere = 1 num //= base return isThere# Function to count the numbers in the# range [1, N] such that it doesn't# contain the digit 'K' in its decimal# and octal representationdef count(n, k, v): # Stores count of numbers in the # range [0, i] that contains the # digit 'K' in its octal or # decimal representation pref = [0]*1000005 # Traverse the range [0, 1e6 + 5] for i in range(1, 10 ** 6 + 5): # Check if i contains the digit # 'K' in its decimal or # octal representation present = contains(i, k, 10) or contains(i, k, 8) # Update pref[i] pref[i] += pref[i - 1] + present # Print the answer of queries for i in range(n): print(v[i][1] - v[i][0] + 1- (pref[v[i][1]]- pref[v[i][0] - 1]),end=" ")# Driver Codeif __name__ == '__main__': K = 7 Q = [ [ 2, 5 ], [ 1, 15 ] ] N = len(Q) # Function Call count(N, K, Q) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to check if the given digit // 'K' is present in the decimal and octal // representations of num or not static bool contains(int num, int K, int Base) { // Stores if the digit exists // or not bool isThere = false; // Iterate till nums is non-zero while (num > 0) { // Find the remainder int remainder = num % Base; // If the remainder is K if (remainder == K) { isThere = true; } num /= Base; } return isThere; } // Function to count the numbers in the // range [1, N] such that it doesn't // contain the digit 'K' in its decimal // and octal representation static void count(int n, int k, List<List<int> > v) { // Stores count of numbers in the // range [0, i] that contains the // digit 'K' in its octal or // decimal representation int[] pref = new int[1000005]; // Traverse the range [0, 1e6 + 5] for (int i = 1; i < 1e6 + 5; i++) { // Check if i contains the digit // 'K' in its decimal or // octal representation bool present = contains(i, k, 10) || contains(i, k, 8); // Update pref[i] if(present) { pref[i] += pref[i - 1] + 1; } } // Print the answer of queries Console.Write((v[0][1] - v[0][0] + 1 - (pref[v[0][1]] - pref[v[0][0] - 1])) + " "); Console.Write((v[1][1] - v[1][0] - (pref[v[1][1]] - pref[v[1][0] - 1])) + " "); } // Driver code static void Main() { int K = 7; List<List<int> > Q = new List<List<int>>(); Q.Add(new List<int>()); Q[0].Add(2); Q[0].Add(5); Q.Add(new List<int>()); Q[1].Add(1); Q[1].Add(15); int N = Q.Count; // Function Call count(N, K, Q); }}// This code is contributed by divyesh072019. |
Javascript
<script>// Javascript program for the above approach// Function to check if the given digit// 'K' is present in the decimal and octal// representations of num or notfunction contains(num, K, base){ // Stores if the digit exists // or not var isThere = 0; // Iterate till nums is non-zero while (num) { // Find the remainder var remainder = num % base; // If the remainder is K if (remainder == K) { isThere = 1; } num /= base; } return isThere;}// Function to count the numbers in the// range [1, N] such that it doesn't// contain the digit 'K' in its decimal// and octal representationfunction count(n, k, v){ // Stores count of numbers in the // range [0, i] that contains the // digit 'K' in its octal or // decimal representation var pref = Array(100005).fill(0); // Traverse the range [0, 1e6 + 5] for (var i = 1; i < 100005; i++) { // Check if i contains the digit // 'K' in its decimal or // octal representation var present = contains(i, k, 10) || contains(i, k, 8); // Update pref[i] pref[i] += pref[i - 1] + present; } // Print the answer of queries for (var i = 0; i < n; ++i) { document.write( v[i][1] - v[i][0] + 1 - (pref[v[i][1]] - pref[v[i][0] - 1]) + ' '); }}// Driver Codevar K = 7;var Q = [ [ 2, 5 ], [1, 15 ]];var N = Q.length;// Function Callcount(N, K, Q);</script> |
Output:
4 13
Time Complexity:O(N*(log 10(N)+log8(N)))
Auxiliary Space: O(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!
