Number of palindromes in a given range
The given problem is to find the number of palindromes within a given range of integers. A palindrome is a number that reads the same backward as forward (e.g., 121, 454, 777). The task is to count the number of palindromes within a specified range (inclusive of the endpoints).
Problem Statement with Example
Let's consider the range from 50 to 300.
- The palindromes in this range are: 55, 66, 77, ..., 252, 262, 272, 282, 292 (total 25 palindromes).
- For the range from 1000 to 1200, the palindromes are: 1001, 1111 (total 2 palindromes).
Pseudocode
function reverse(number):
result = 0
while number > 0:
result = (result * 10) + (number % 10)
number = number / 10
return result
function countPalindromesInRange(s, e):
if s < 0 or e < 0:
return
count = 0
for i from s to e-1:
if reverse(i) == i:
count = count + 1
display count
Algorithm Explanation
-
The
reverse
function takes an integer as input and returns its reverse. It uses a while loop to obtain the reverse by continuously extracting the last digit of the number and appending it to the result variable. -
The
countPalindromesInRange
function takes two integers, s and e, as input, which represent the start and end of the range, respectively. -
We initialize a
count
variable to store the number of palindromes found within the range. -
We use a for loop to iterate over all numbers from s to e-1 (inclusive).
-
For each number in the range, we check if it is a palindrome by calling the
reverse
function and comparing the reversed number with the original number. If they are the same, it means the number is a palindrome, and we increment thecount
variable. -
After processing all numbers in the range, we display the value of
count
, which represents the total number of palindromes found.
Code Solution
Here given code implementation process.
/*
C program for
Number of palindromes in a given range
*/
#include <stdio.h>
// Returns the Reversal view of given number
int reverse(int number)
{
int result = 0;
while (number > 0)
{
// Append digit
result = (result *10) + (number % 10);
//remove last digit
number /= 10;
}
return result;
}
// Handles the request of count number of palindrome in given range
void countPalindromesInRange(int s, int e)
{
if (s < 0 || e < 0)
{
return;
}
int count = 0;
// Execute loop in given range
for (int i = s; i < e; ++i)
{
if (reverse(i) == i)
{
// When i is palindrome
count++;
}
}
// Display result
printf("\n Number of palindromes in range (%d %d) is : %d", s, e, count);
}
int main(int argc, char
const *argv[])
{
// Test
countPalindromesInRange(50, 300);
countPalindromesInRange(1000, 1200);
return 0;
}
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
/*
Java program for
Number of palindromes in a given range
*/
public class Palindrome
{
// Returns the Reversal view of given number
public int reverse(int number)
{
int result = 0;
while (number > 0)
{
// Append digit
result = (result * 10) + (number % 10);
//remove last digit
number /= 10;
}
return result;
}
// Handles the request of count number of palindrome in given range
public void countPalindromesInRange(int s, int e)
{
if (s < 0 || e < 0)
{
return;
}
int count = 0;
// Execute loop in given range
for (int i = s; i < e; ++i)
{
if (reverse(i) == i)
{
count++;
}
}
// Display result
System.out.print("\n Number of palindromes in range (" + s + " " + e + ") is : " + count );
}
public static void main(String[] args)
{
Palindrome task = new Palindrome();
// Test
task.countPalindromesInRange(50, 300);
task.countPalindromesInRange(1000, 1200);
}
}
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Number of palindromes in a given range
*/
class Palindrome
{
public:
// Returns the Reversal view of given number
int reverse(int number)
{
int result = 0;
while (number > 0)
{
// Append digit
result = (result *10) + (number % 10);
//remove last digit
number /= 10;
}
return result;
}
// Handles the request of count number of palindrome in given range
void countPalindromesInRange(int s, int e)
{
if (s < 0 || e < 0)
{
return;
}
int count = 0;
// Execute loop in given range
for (int i = s; i < e; ++i)
{
if (this->reverse(i) == i)
{
count++;
}
}
// Display result
cout << "\n Number of palindromes in range ("
<< s << " " << e << ") is : " << count;
}
};
int main()
{
Palindrome *task = new Palindrome();
// Test
task->countPalindromesInRange(50, 300);
task->countPalindromesInRange(1000, 1200);
return 0;
}
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
// Include namespace system
using System;
/*
Csharp program for
Number of palindromes in a given range
*/
public class Palindrome
{
// Returns the Reversal view of given number
public int reverse(int number)
{
int result = 0;
while (number > 0)
{
// Append digit
result = (result * 10) + (number % 10);
//remove last digit
number /= 10;
}
return result;
}
// Handles the request of count number of palindrome in given range
public void countPalindromesInRange(int s, int e)
{
if (s < 0 || e < 0)
{
return;
}
int count = 0;
// Execute loop in given range
for (int i = s; i < e; ++i)
{
if (this.reverse(i) == i)
{
count++;
}
}
// Display result
Console.Write("\n Number of palindromes in range (" +
s + " " + e + ") is : " + count);
}
public static void Main(String[] args)
{
Palindrome task = new Palindrome();
// Test
task.countPalindromesInRange(50, 300);
task.countPalindromesInRange(1000, 1200);
}
}
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
package main
import "fmt"
/*
Go program for
Number of palindromes in a given range
*/
// Returns the Reversal view of given number
func reverse(number int) int {
var result int = 0
for (number > 0) {
// Append digit
result = (result * 10) + (number % 10)
//remove last digit
number = number / 10
}
return result
}
// Handles the request of count number of palindrome in given range
func countPalindromesInRange(s, e int) {
if s < 0 || e < 0 {
return
}
var count int = 0
// Execute loop in given range
for i := s ; i < e ; i++ {
if reverse(i) == i {
count++
}
}
// Display result
fmt.Print("\n Number of palindromes in range (",
s, " ", e, ") is : ", count)
}
func main() {
// Test
countPalindromesInRange(50, 300)
countPalindromesInRange(1000, 1200)
}
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
<?php
/*
Php program for
Number of palindromes in a given range
*/
class Palindrome
{
// Returns the Reversal view of given number
public function reverse($number)
{
$result = 0;
while ($number > 0)
{
// Append digit
$result = ($result * 10) + ($number % 10);
//remove last digit
$number = (int)($number / 10);
}
return $result;
}
// Handles the request of count number of palindrome in given range
public function countPalindromesInRange($s, $e)
{
if ($s < 0 || $e < 0)
{
return;
}
$count = 0;
// Execute loop in given range
for ($i = $s; $i < $e; ++$i)
{
if ($this->reverse($i) == $i)
{
$count++;
}
}
// Display result
echo("\n Number of palindromes in range (".$s." ".$e.") is : ".$count);
}
}
function main()
{
$task = new Palindrome();
// Test
$task->countPalindromesInRange(50, 300);
$task->countPalindromesInRange(1000, 1200);
}
main();
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
/*
Node JS program for
Number of palindromes in a given range
*/
class Palindrome
{
// Returns the Reversal view of given number
reverse(number)
{
var result = 0;
while (number > 0)
{
// Append digit
result = (result * 10) + (number % 10);
//remove last digit
number = parseInt(number / 10);
}
return result;
}
// Handles the request of count number of palindrome in given range
countPalindromesInRange(s, e)
{
if (s < 0 || e < 0)
{
return;
}
var count = 0;
// Execute loop in given range
for (var i = s; i < e; ++i)
{
if (this.reverse(i) == i)
{
count++;
}
}
// Display result
process.stdout.write("\n Number of palindromes in range (" +
s + " " + e + ") is : " + count);
}
}
function main()
{
var task = new Palindrome();
// Test
task.countPalindromesInRange(50, 300);
task.countPalindromesInRange(1000, 1200);
}
main();
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
# Python 3 program for
# Number of palindromes in a given range
class Palindrome :
# Returns the Reversal view of given number
def reverse(self, number) :
result = 0
while (number > 0) :
# Append digit
result = (result * 10) + (number % 10)
# remove last digit
number = int(number / 10)
return result
# Handles the request of count number of palindrome in given range
def countPalindromesInRange(self, s, e) :
if (s < 0 or e < 0) :
return
count = 0
i = s
# Execute loop in given range
while (i < e) :
if (self.reverse(i) == i) :
count += 1
i += 1
# Display result
print("\n Number of palindromes in range (",
s ," ", e ,") is : ", count, end = "")
def main() :
task = Palindrome()
# Test
task.countPalindromesInRange(50, 300)
task.countPalindromesInRange(1000, 1200)
if __name__ == "__main__": main()
Output
Number of palindromes in range ( 50 300 ) is : 25
Number of palindromes in range ( 1000 1200 ) is : 2
# Ruby program for
# Number of palindromes in a given range
class Palindrome
# Returns the Reversal view of given number
def reverse(number)
result = 0
while (number > 0)
# Append digit
result = (result * 10) + (number % 10)
# remove last digit
number = number / 10
end
return result
end
# Handles the request of count number of palindrome in given range
def countPalindromesInRange(s, e)
if (s < 0 || e < 0)
return
end
count = 0
i = s
# Execute loop in given range
while (i < e)
if (self.reverse(i) == i)
count += 1
end
i += 1
end
# Display result
print("\n Number of palindromes in range (",
s ," ", e ,") is : ", count)
end
end
def main()
task = Palindrome.new()
# Test
task.countPalindromesInRange(50, 300)
task.countPalindromesInRange(1000, 1200)
end
main()
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
/*
Scala program for
Number of palindromes in a given range
*/
class Palindrome()
{
// Returns the Reversal view of given number
def reverse(num: Int): Int = {
var result: Int = 0;
var number = num;
while (number > 0)
{
// Append digit
result = (result * 10) + (number % 10);
//remove last digit
number = number / 10;
}
return result;
}
// Handles the request of count number of palindrome in given range
def countPalindromesInRange(s: Int, e: Int): Unit = {
if (s < 0 || e < 0)
{
return;
}
var count: Int = 0;
var i: Int = s;
// Execute loop in given range
while (i < e)
{
if (reverse(i) == i)
{
count += 1;
}
i += 1;
}
// Display result
print("\n Number of palindromes in range (" +
s + " " + e + ") is : " + count);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Palindrome = new Palindrome();
// Test
task.countPalindromesInRange(50, 300);
task.countPalindromesInRange(1000, 1200);
}
}
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
/*
Swift 4 program for
Number of palindromes in a given range
*/
class Palindrome
{
// Returns the Reversal view of given number
func reverse(_ num: Int) -> Int
{
var result: Int = 0;
var number: Int = num;
while (number > 0)
{
// Append digit
result = (result * 10) + (number % 10);
// remove last digit
number = number / 10;
}
return result;
}
// Handles the request of count number of palindrome in given range
func countPalindromesInRange(_ s: Int, _ e: Int)
{
if (s < 0 || e < 0)
{
return;
}
var count: Int = 0;
var i: Int = s;
// Execute loop in given range
while (i < e)
{
if (self.reverse(i) == i)
{
count += 1;
}
i += 1;
}
// Display result
print("\n Number of palindromes in range (",
s ,"", e ,") is : ", count, terminator: "");
}
}
func main()
{
let task: Palindrome = Palindrome();
// Test
task.countPalindromesInRange(50, 300);
task.countPalindromesInRange(1000, 1200);
}
main();
Output
Number of palindromes in range ( 50 300 ) is : 25
Number of palindromes in range ( 1000 1200 ) is : 2
/*
Kotlin program for
Number of palindromes in a given range
*/
class Palindrome
{
// Returns the Reversal view of given number
fun reverse(num: Int): Int
{
var result: Int = 0;
var number: Int = num;
while (number > 0)
{
// Append digit
result = (result * 10) + (number % 10);
//remove last digit
number = number / 10;
}
return result;
}
// Handles the request of count number of palindrome in given range
fun countPalindromesInRange(s: Int, e: Int): Unit
{
if (s < 0 || e < 0)
{
return;
}
var count: Int = 0;
var i: Int = s;
// Execute loop in given range
while (i < e)
{
if (this.reverse(i) == i)
{
count += 1;
}
i += 1;
}
// Display result
print("\n Number of palindromes in range (" +
s + " " + e + ") is : " + count);
}
}
fun main(args: Array < String > ): Unit
{
val task: Palindrome = Palindrome();
// Test
task.countPalindromesInRange(50, 300);
task.countPalindromesInRange(1000, 1200);
}
Output
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
Resultant Output Explanation
When the program runs with the given test cases, the output is as follows:
Number of palindromes in range (50 300) is : 25
Number of palindromes in range (1000 1200) is : 2
The program correctly counts the number of palindromes in the specified ranges and displays the results.
Time Complexity
The time complexity of the provided solution is O(N*M), where N is the number of integers in the range (e-s), and M is the average number of digits in each integer.
The countPalindromesInRange
function iterates through all numbers in the range, and for each number, it
calls the reverse
function, which takes time proportional to the number of digits in the number (M).
So, the overall time complexity is O(N*M). In practice, this solution should be efficient for relatively small
ranges, but for larger ranges, it may not be optimal.
To improve the time complexity, we can use a more efficient algorithm that doesn't require reversing the entire number, but that would require a different approach and code modification.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment