Given an integer K and a range of consecutive numbers [L, R]. The task is to count the numbers from the given range which have digital root as K (1 ? K ? 9). Digital root is sum of digits of a number until it becomes a single digit number. For example, 256 -> 2 + 5 + 6 = 13 -> 1 + 3 = 4.
Examples:
Input: L = 10, R = 22, K = 3
Output: 2
12 and 21 are the only numbers from the range whose digit sum is 3.Input: L = 100, R = 200, K = 5
Output: 11
Approach:
- First thing is to note that for any number Sum of Digits is equal to Number % 9. If remainder is 0, then sum of digits is 9.
- So if K = 9, then replace K with 0.
- Task, now is to find count of numbers in range L to R with modulo 9 equal to K.
- Divide the entire range into the maximum possible groups of 9 starting with L (TotalRange / 9), since in each range there will be exactly one number with modulo 9 equal to K.
- Loop over rest number of elements from R to R – count of rest elements, and check if any number satisfies the condition.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define ll long long intusing namespace std;// Function to return the count// of required numbersint countNumbers(int L, int R, int K){ if (K == 9) K = 0; // Count of numbers present // in given range int totalnumbers = R - L + 1; // Number of groups of 9 elements // starting from L int factor9 = totalnumbers / 9; // Left over elements not covered // in factor 9 int rem = totalnumbers % 9; // One Number in each group of 9 int ans = factor9; // To check if any number in rem // satisfy the property for (int i = R; i > R - rem; i--) { int rem1 = i % 9; if (rem1 == K) ans++; } return ans;}// Driver codeint main(){ int L = 10; int R = 22; int K = 3; cout << countNumbers(L, R, K); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function to return the count// of required numbers static int countNumbers(int L, int R, int K) { if (K == 9) { K = 0; } // Count of numbers present // in given range int totalnumbers = R - L + 1; // Number of groups of 9 elements // starting from L int factor9 = totalnumbers / 9; // Left over elements not covered // in factor 9 int rem = totalnumbers % 9; // One Number in each group of 9 int ans = factor9; // To check if any number in rem // satisfy the property for (int i = R; i > R - rem; i--) { int rem1 = i % 9; if (rem1 == K) { ans++; } } return ans; }// Driver code public static void main(String[] args) { int L = 10; int R = 22; int K = 3; System.out.println(countNumbers(L, R, K)); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approach# Function to return the count# of required numbersdef countNumbers(L, R, K): if (K == 9): K = 0 # Count of numbers present # in given range totalnumbers = R - L + 1 # Number of groups of 9 elements # starting from L factor9 = totalnumbers // 9 # Left over elements not covered # in factor 9 rem = totalnumbers % 9 # One Number in each group of 9 ans = factor9 # To check if any number in rem # satisfy the property for i in range(R, R - rem, -1): rem1 = i % 9 if (rem1 == K): ans += 1 return ans# Driver codeL = 10R = 22K = 3print(countNumbers(L, R, K))# This code is contributed # by mohit kumar |
C#
// C# implementation of the approachusing System ;class GFG { // Function to return the count // of required numbers static int countNumbers(int L, int R, int K) { if (K == 9) { K = 0; } // Count of numbers present // in given range int totalnumbers = R - L + 1; // Number of groups of 9 elements // starting from L int factor9 = totalnumbers / 9; // Left over elements not covered // in factor 9 int rem = totalnumbers % 9; // One Number in each group of 9 int ans = factor9; // To check if any number in rem // satisfy the property for (int i = R; i > R - rem; i--) { int rem1 = i % 9; if (rem1 == K) { ans++; } } return ans; } // Driver code public static void Main() { int L = 10; int R = 22; int K = 3; Console.WriteLine(countNumbers(L, R, K)); }}/* This code is contributed by Ryuga */ |
PHP
<?php// PHP implementation of the approach// Function to return the count// of required numbersfunction countNumbers($L, $R, $K){ if ($K == 9) $K = 0; // Count of numbers present // in given range $totalnumbers = $R - $L + 1; // Number of groups of 9 elements // starting from L $factor9 = intval($totalnumbers / 9); // Left over elements not covered // in factor 9 $rem = $totalnumbers % 9; // One Number in each group of 9 $ans = $factor9; // To check if any number in rem // satisfy the property for ($i = $R; $i > $R - $rem; $i--) { $rem1 = $i % 9; if ($rem1 == $K) $ans++; } return $ans;}// Driver code$L = 10;$R = 22;$K = 3;echo countNumbers($L, $R, $K);// This code is contributed by Ita_c?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the count// of required numbersfunction countNumbers(L, R, K) { if (K == 9) { K = 0; } // Count of numbers present // in given range var totalnumbers = R - L + 1; // Number of groups of 9 elements // starting from L var factor9 = totalnumbers / 9; // Left over elements not covered // in factor 9 var rem = totalnumbers % 9; // One Number in each group of 9 var ans = factor9; // To check if any number in rem // satisfy the property for(var i = R; i > R - rem; i--) { var rem1 = i % 9; if (rem1 == K) { ans++; } } return ans;} // Driver Codevar L = 10;var R = 22;var K = 3;document.write(Math.round(countNumbers(L, R, K)));// This code is contributed by Ankita saini </script> |
Output:
2
Time Complexity: O(R)
Auxiliary Space: O(1)
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!
