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++
#include <iostream>
using namespace std;
bool isRevDiffDivisible( int x, int k)
{
int n = x;
int m = 0;
int flag;
while (x > 0)
{
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;
}
int main()
{
int l = 20, r = 23, k = 6;
cout << countNumbers(l, r, k) << endl;
return 0;
}
|
Java
import java.io.*;
import java.math.*;
class GFG {
static boolean isRevDiffDivisible( int x, int k)
{
int n = x;
int m = 0 ;
int flag;
while (x > 0 )
{
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;
}
public static void main(String args[])
{
int l = 35 , r = 45 , k = 5 ;
System.out.println(countNumbers(l, r, k));
}
}
|
Python3
def isRevDiffDivisible(x, k) :
n = x; m = 0
while (x > 0 ) :
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
l = 20 ; r = 23 ; k = 6
print (countNumbers(l, r, k))
|
C#
using System;
class GFG {
static bool isRevDiffDivisible( int x, int k)
{
int n = x;
int m = 0;
while (x > 0)
{
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;
}
public static void Main()
{
int l = 35, r = 45, k = 5;
Console.WriteLine(countNumbers(l, r, k));
}
}
|
Javascript
<script>
function isRevDiffDivisible(x , k)
{
var n = x;
var m = 0;
var flag;
while (x > 0)
{
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;
}
var l = 35, r = 45, k = 5;
document.write(countNumbers(l, r, k));
</script>
|
PHP
<?php
function isRevDiffDivisible( $x , $k )
{
$n = $x ;
$m = 0;
$flag ;
while ( $x > 0)
{
$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 ;
}
$l = 20; $r = 23; $k = 6;
echo countNumbers( $l , $r , $k );
?>
|
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.
C++
#include <iostream>
#include <cmath>
int countNumbers( int start, int end, int k) {
int count = 0;
for ( int num = start; num <= end; ++num) {
int reversedNum = 0;
int originalNum = num;
while (originalNum > 0) {
reversedNum = reversedNum * 10 + originalNum % 10;
originalNum /= 10;
}
int diff = std:: abs (num - reversedNum);
if (diff % k == 0) {
count++;
}
}
return count;
}
int main() {
int start = 35;
int end = 45;
int k = 5;
std::cout << countNumbers(start, end, k) << std::endl;
return 0;
}
|
Java
public class Main {
static int countNumbers( int start, int end, int k) {
int count = 0 ;
for ( int num = start; num <= end; ++num) {
int diff = Math.abs(num - Integer.parseInt( new StringBuilder(Integer.toString(num)).reverse().toString()));
if (diff % k == 0 ) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int start = 35 ;
int end = 45 ;
int k = 5 ;
System.out.println(countNumbers(start, end, k));
}
}
|
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 count
start = 35
end = 45
k = 5
print (count_numbers(start, end, k))
|
C#
using System;
class Program
{
static int CountNumbers( int start, int end, int k)
{
int count = 0;
for ( int num = start; num <= end; ++num)
{
int reversedNum = 0;
int originalNum = num;
while (originalNum > 0)
{
reversedNum = reversedNum * 10 + originalNum % 10;
originalNum /= 10;
}
int diff = Math.Abs(num - reversedNum);
if (diff % k == 0)
{
count++;
}
}
return count;
}
static void Main()
{
int start = 35;
int end = 45;
int k = 5;
Console.WriteLine(CountNumbers(start, end, k));
}
}
|
Javascript
function GFG(start, end, k) {
let count = 0;
for (let num = start; num <= end; num++) {
const diff = Math.abs(num - parseInt(num.toString().split( '' ).reverse().join( '' )));
if (diff % k === 0) {
count++;
}
}
return count;
}
const start = 35;
const end = 45;
const k = 5;
console.log(GFG(start, end, k));
|
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).