Given two positive integers N and M, the task is to find the count of all possible numbers in the range [1, M], having suffix as N.
Examples:
Input: N = 5, M = 15
Output: 2
Explanation: Only numbers satisfying the conditions are {5, 15}.
Input: N = 25, M = 4500
Output : 45
Naive Approach: The simplest approach is to traverse all integers in the range [1, M] and check if the suffix is N or not.
Time Complexity: O(M)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, following observation needs to be made:
Let N = 5 and M = 100
The Suffix numbers are 5, 15, 25, 35…95, which forms an Arithmetic Progression with
first term = 5, last term = 95, common difference = Base of N (eg: 6 has base 10, 45 has base 100 which is nothing but the exponentiation of the form 10digitsOf(N), where digitsOf(N) = no. of digits present in N.
Therefore, in order to calculate the count of possible numbers in the range [1, M], the following expression needs to be evaluated:
Count of numbers = Number of terms in the series = (tn – a)/d + 1 , where
tn is the last term of the sequence, a is the first term of the sequence, d is the common difference = (ti+1 – ti), i = 1, 2, 3…n-1
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count the// no. of digits of Nint digitsOf(int num){ return to_string(num).size();}// Function to count all possible// numbers having Suffix as Nint count(int a, int tn){ // Difference of the A.P int diff = pow(10, digitsOf(a)); // Count of the number of terms return ((tn - a) / diff) + 1;}// Driver Codeint main(){ int n, m; n = 25, m = 4500; cout << count(n, m); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{// Function to count the// no. of digits of Nstatic int digitsOf(int num){ return Integer.toString(num).length();}// Function to count all possible// numbers having Suffix as Nstatic int count(int a, int tn){ // Difference of the A.P int diff = (int)Math.pow(10, digitsOf(a)); // Count of the number of terms return ((tn - a) / diff) + 1;}// Driver codepublic static void main (String[] args){ int n = 25, m = 4500; System.out.println(count(n, m));}}// This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach # Function to count the# no. of digits of Ndef digitsOf(num): return len(str(num));# Function to count all possible# numbers having Suffix as Ndef count(a, tn): # Difference of the A.P diff = int(pow(10, digitsOf(a))); # Count of the number of terms return ((tn - a) / diff) + 1;# Driver codeif __name__ == '__main__': n = 25; m = 4500; print(int(count(n, m)));# This code is contributed by sapnasingh4991 |
C#
// C# program to implement // the above approach using System;class GFG{// Function to count the// no. of digits of Nstatic int digitsOf(int num){ return num.ToString().Length;}// Function to count all possible// numbers having Suffix as Nstatic int count(int a, int tn){ // Difference of the A.P int diff = (int)Math.Pow(10, digitsOf(a)); // Count of the number of terms return ((tn - a) / diff) + 1;}// Driver codepublic static void Main(String[] args){ int n = 25, m = 4500; Console.WriteLine(count(n, m));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript program to implement// the above approach// Function to count the// no. of digits of Nfunction digitsOf(num){ return num.toString().length;} // Function to count all possible// numbers having Suffix as Nfunction count(a, tn){ // Difference of the A.P let diff = Math.floor(Math.pow(10, digitsOf(a))); // Count of the number of terms return Math.floor((tn - a) / diff) + 1;}// Driver Code let n = 25, m = 4500; document.write(count(n, m)); </script> |
45
Time Complexity: O(log10(k)) where k is the number of digits in n.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
