Given two number l and r. Count the total numbers between l and r which when subtracted from their respective reverse, the difference is a product of k.
Examples:
Input : 20 23 6
Output : 2
20 and 22 are the two numbers.
|20-2| = 18 which is a product of 6
|22-22| = 0 which is a product of 6
Input : 35 45 5
Output : 2
38 and 44 are the two numbers.
|38-83| = 45 which is a product of 5
|44-44| = 0 which is a product of 5
Approach: For each number between the given range check if the difference between the number and its reverse number is divisible by k, increment count if yes.
C++
// C++ program to Count the numbers// within a given range in which when// you subtract a number from its// reverse, the difference is a product// of k#include <iostream>using namespace std;bool isRevDiffDivisible(int x, int k){ // function to check if the number // and its reverse have their // absolute difference divisible by k int n = x; int m = 0; int flag; while (x > 0) { // reverse the number m = m * 10 + x % 10; x /= 10; } return (abs(n - m) % k == 0);}int countNumbers(int l, int r, int k){ int count = 0; for (int i = l; i <= r; i++) if (isRevDiffDivisible(i, k)) ++count; return count;}// Driver codeint main(){ int l = 20, r = 23, k = 6; cout << countNumbers(l, r, k) << endl; return 0;} |
Java
// Java program to Count the // numbers within a given range // in which when you subtract // a number from its reverse, // the difference is a product of kimport java.io.*;import java.math.*;class GFG { static boolean isRevDiffDivisible(int x, int k) { // function to check if the number // and its reverse have their // absolute difference divisible by k int n = x; int m = 0; int flag; while (x > 0) { // reverse the number m = m * 10 + x % 10; x /= 10; } return (Math.abs(n - m) % k == 0); } static int countNumbers(int l, int r, int k) { int count = 0; for (int i = l; i <= r; i++) if (isRevDiffDivisible(i, k)) ++count; return count; } // Driver code public static void main(String args[]) { int l = 35, r = 45, k = 5; System.out.println(countNumbers(l, r, k)); }}// This code is contributed // by Nikita Tiwari. |
Python3
# Python 3 program to Count the numbers# within a given range in which when you# subtract a number from its reverse,# the difference is a product of kdef isRevDiffDivisible(x, k) : # function to check if the number # and its reverse have their # absolute difference divisible by k n = x; m = 0 while (x > 0) : # Reverse the number m = m * 10 + x % 10 x = x // 10 return (abs(n - m) % k == 0)def countNumbers(l, r, k) : count = 0 for i in range(l, r + 1) : if (isRevDiffDivisible(i, k)) : count = count + 1 return count # Driver codel = 20; r = 23; k = 6print(countNumbers(l, r, k))# This code is contributed by Nikita Tiwari. |
C#
// C# program to Count the // numbers within a given range // in which when you subtract // a number from its reverse, // the difference is a product of kusing System;class GFG { static bool isRevDiffDivisible(int x, int k) { // function to check if the number // and its reverse have their // absolute difference divisible by k int n = x; int m = 0; // int flag; while (x > 0) { // reverse the number m = m * 10 + x % 10; x /= 10; } return (Math.Abs(n - m) % k == 0); } static int countNumbers(int l, int r, int k) { int count = 0; for (int i = l; i <= r; i++) if (isRevDiffDivisible(i, k)) ++count; return count; } // Driver code public static void Main() { int l = 35, r = 45, k = 5; Console.WriteLine(countNumbers(l, r, k)); }}// This code is contributed // by vt_m. |
Javascript
<script>// javascript program to Count the // numbers within a given range // in which when you subtract // a number from its reverse, // the difference is a product of kfunction isRevDiffDivisible(x , k){ // function to check if the number // and its reverse have their // absolute difference divisible by k var n = x; var m = 0; var flag; while (x > 0) { // reverse the number m = m * 10 + x % 10; x = parseInt(x/10); } return (Math.abs(n - m) % k == 0);}function countNumbers(l , r , k){ var count = 0; for (i = l; i <= r; i++) if (isRevDiffDivisible(i, k)) count++; return count;} // Driver codevar l = 35, r = 45, k = 5;document.write(countNumbers(l, r, k));// This code contributed by Princi Singh</script> |
PHP
<?php// PHP program to Count the // numbers within a given // range in which when you// subtract a number from // its reverse, the difference // is a product of kfunction isRevDiffDivisible($x, $k){ // function to check if // the number and its // reverse have their // absolute difference // divisible by k $n = $x; $m = 0; $flag; while ($x > 0) { // reverse the number $m = $m * 10 + $x % 10; $x = (int)$x / 10; } return (abs($n - $m) % $k == 0);}function countNumbers($l, $r, $k){ $count = 0; for ($i = $l; $i <= $r; $i++) if (isRevDiffDivisible($i, $k)) ++$count; return $count;}// Driver code$l = 20; $r = 23; $k = 6;echo countNumbers($l, $r, $k); // This code is contributed by mits.?> |
2
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Approach#2: Using abs
The given approach is a Python function named “count_numbers” that takes three arguments, start, end, and k, and returns the count of numbers in the range [start, end] that satisfy a particular condition. The condition is that the absolute difference between a number and its reverse is divisible by k.
Algorithm
1. Initialize a variable “count” to 0 to store the count of numbers that satisfy the condition.
2. Use a for loop to iterate over all the numbers in the range [start, end].
3. For each number, compute the absolute difference between the number and its reverse by first converting the number to a string, reversing it, and then converting it back to an integer.
4. If the absolute difference is divisible by k, increment the count variable by 1.
5. After iterating over all the numbers in the range, return the count.
Python3
def count_numbers(start, end, k): count = 0 for num in range(start, end+1): diff = abs(num - int(str(num)[::-1])) if diff % k == 0: count += 1 return countstart = 35end = 45k = 5print(count_numbers(start, end, k)) |
Javascript
function GFG(start, end, k) { let count = 0; // Iterate through numbers from 'start' to 'end' for (let num = start; num <= end; num++) { // Calculate the absolute difference between // 'num' and its reverse const diff = Math.abs(num - parseInt(num.toString().split('').reverse().join(''))); // Check if the difference is divisible by 'k' if (diff % k === 0) { count++; } } return count;}const start = 35;const end = 45;const k = 5;console.log(GFG(start, end, k)); |
2
Time Complexity: O(NM), where N is the difference between the start and end, and M is the length of the maximum number in the range [start, end]. The reason for this time complexity is that for each number in the range, we need to convert it to a string, reverse it, and then convert it back to an integer. This requires M operations for each number. Therefore, the total number of operations is NM.
Space Complexity: O(M), where M is the length of the maximum number in the range [start, end]. The reason for this space complexity is that we need to convert each number in the range to a string, and the length of the string is at most M. Therefore, the total space required is N*M. However, since we only store one number at a time, the actual space used at any given time is O(M).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
