Given two integers L and R denoting the starting and end values of a range, the task is to count all numbers in that range whose all digit are same, like 1, 22, 444, 3333, etc.
Example:
Input: L = 12, R = 68
Output: 5
Explanation:
{ 22, 33, 44, 55, 66} are the numbers with same digits in the given range.
Input: L = 1, R = 32
Output: 11
Naive Approach: Iterate through all the numbers from L to R and for each number, check if it has all its digits same. If yes, then increase the required count. Print this count at the end.
Efficient Approach: The idea is based on the fact that the multiples (1 to 9) of 1, 11, 111, etc has all its digits same.
For example:
1 times 1 = 1 (All digits are same)
2 times 1 = 2 (All digits are same)
3 times 1 = 3 (All digits are same)
.
.
9 times 1 = 9 (All digits are same)
Similarly
1 times 11 = 11 (All digits are same)
2 times 11 = 22 (All digits are same)
3 times 11 = 33 (All digits are same)
.
.
9 times 11 = 99 (All digits are same)
Same is the case for 111, 1111, etc.
Therefore, the steps can be defined as:
- Find the number of digits in R. This will decide the length of consecutive 1s to be created, till which we have to check.
For example, if R = 100, then length(R) = 3. Therefore we need to check only the multiples of 1, 11, and 111.
- For each length of consecutive 1s from 1 to length(R):
- Multiply them with all values from 2 to 9
- Check if it lies within the range [L, R] or not.
- If yes, then increment the count of required numbers.
- Print the required count of numbers.
C++
#include <bits/stdc++.h>
using namespace std;
int count_same_digit( int L, int R)
{
int tmp = 0, ans = 0;
int n = log10 (R) + 1;
for ( int i = 0; i < n; i++) {
tmp = tmp * 10 + 1;
for ( int j = 1; j <= 9; j++) {
if (L <= (tmp * j)
&& (tmp * j) <= R) {
ans++;
}
}
}
return ans;
}
int main()
{
int L = 12, R = 68;
cout << count_same_digit(L, R)
<< endl;
return 0;
}
|
Java
import java.util.*;
class GFG{
static int count_same_digit( int L, int R)
{
int tmp = 0 , ans = 0 ;
int n = ( int )Math.log10(R) + 1 ;
for ( int i = 0 ; i < n; i++)
{
tmp = tmp * 10 + 1 ;
for ( int j = 1 ; j <= 9 ; j++)
{
if (L <= (tmp * j) && (tmp * j) <= R)
{
ans++;
}
}
}
return ans;
}
public static void main(String[] args)
{
int L = 12 , R = 68 ;
System.out.println(count_same_digit(L, R));
}
}
|
Python3
import math
def count_same_digit(L, R):
tmp = 0 ; ans = 0 ;
n = int (math.log10(R) + 1 );
for i in range ( 0 , n):
tmp = tmp * 10 + 1 ;
for j in range ( 1 , 9 ):
if (L < = (tmp * j) and (tmp * j) < = R):
ans + = 1 ;
return ans;
L = 12 ; R = 68 ;
print (count_same_digit(L, R))
|
C#
using System;
class GFG{
static int count_same_digit( int L, int R)
{
int tmp = 0, ans = 0;
int n = ( int )Math.Log10(R) + 1;
for ( int i = 0; i < n; i++)
{
tmp = tmp * 10 + 1;
for ( int j = 1; j <= 9; j++)
{
if (L <= (tmp * j) && (tmp * j) <= R)
{
ans++;
}
}
}
return ans;
}
public static void Main()
{
int L = 12, R = 68;
Console.Write(count_same_digit(L, R));
}
}
|
Javascript
<script>
function count_same_digit( L, R)
{
var tmp = 0, ans = 0;
var n = Math.log10(R) + 1;
for (let i = 0; i < n; i++) {
tmp = tmp * 10 + 1;
for (let j = 1; j <= 9; j++) {
if (L <= (tmp * j)
&& (tmp * j) <= R) {
ans++;
}
}
}
return ans;
}
var L = 12, R = 68;
document.write( count_same_digit(L, R));
</script>
|
Time Complexity: O(9*d), where d is the number of digits in R.
Space Complexity: O(1)
Another approach without using math –
In the below approach we will convert each of the numbers into strings and check whether their reverse is same as of the real number, if so then we will increment our variable each time by one. In this approach we can simply print out the numbers too which have same digits in a given range.
C++
#include <iostream>
#include <string>
using namespace std;
int count_same( int s, int e)
{
int count = 0;
for ( int i = s; i <= e; i++) {
if (to_string(i)
== string(to_string(i).rbegin(),
to_string(i).rend())
.substr(0, to_string(i).length())) {
count++;
}
}
return count;
}
int main()
{
cout << count_same(12, 68) << endl;
return 0;
}
|
Java
public class Main {
public static int count_same( int s, int e) {
int count = 0 ;
for ( int i = s; i <= e; i++) {
if (Integer.toString(i).equals( new StringBuilder(Integer.toString(i)).reverse().toString())) {
count++;
}
}
return count;
}
public static void main(String[] args) {
System.out.println(count_same( 12 , 68 ));
}
}
|
Python3
def count_same(s,e):
count = 0
for i in range (s,e + 1 ):
if str (i) = = str (i)[:: - 1 ]:
count + = 1
return count
print (count_same( 12 , 68 ))
|
C#
using System;
using System.Linq;
public class MainClass {
public static int CountSame( int s, int e) {
int count = 0;
for ( int i = s; i <= e; i++) {
if (i.ToString() == new string (i.ToString().Reverse().ToArray())) {
count++;
}
}
return count;
}
public static void Main( string [] args) {
Console.WriteLine(CountSame(12, 68));
}
}
|
Javascript
function count_same(s, e) {
let count = 0;
for (let i = s; i <= e; i++) {
if (i.toString() === i.toString().split( '' ).reverse().join( '' )) {
count++;
}
}
return count;
}
console.log(count_same(12, 68));
|
If we now want to print those numbers as well then we need to make a little change to our code –
C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector< int > count_same( int s, int e) {
vector< int > nums;
for ( int i = s; i <= e; i++) {
string num_str = to_string(i);
string rev_num_str = string(num_str.rbegin(), num_str.rend());
if (num_str == rev_num_str) {
nums.push_back(i);
}
}
return nums;
}
int main() {
vector< int > result = count_same(12, 68);
for ( int i = 0; i < result.size(); i++) {
cout << result[i] << " " ;
}
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<Integer> countSame( int s, int e)
{
List<Integer> nums = new ArrayList<>();
for ( int i = s; i <= e; i++) {
String numStr = Integer.toString(i);
String revNumStr = new StringBuilder(numStr)
.reverse()
.toString();
if (numStr.equals(revNumStr)) {
nums.add(i);
}
}
return nums;
}
public static void main(String[] args)
{
List<Integer> result = countSame( 12 , 68 );
for ( int i = 0 ; i < result.size(); i++) {
System.out.print(result.get(i) + " " );
}
}
}
|
Python3
def count_same(s,e):
nums = []
for i in range (s,e + 1 ):
if str (i) = = str (i)[:: - 1 ]:
nums.append(i)
return nums
print (count_same( 12 , 68 ))
|
C#
using System;
using System.Collections.Generic;
class GFG {
public static List< int > CountSame( int s, int e)
{
List< int > nums = new List< int >();
for ( int i = s; i <= e; i++) {
string numStr = i.ToString();
char [] charArray = numStr.ToCharArray();
Array.Reverse(charArray);
string revNumStr = new string (charArray);
if (numStr == revNumStr) {
nums.Add(i);
}
}
return nums;
}
public static void Main( string [] args)
{
List< int > result = CountSame(12, 68);
foreach ( int num in result)
{
Console.Write(num + " " );
}
}
}
|
Javascript
function count_same(s, e) {
let nums = [];
for (let i = s; i <= e; i++) {
if (i.toString() === i.toString().split( '' ).reverse().join( '' )) {
nums.push(i);
}
}
return nums;
}
console.log(count_same(12, 68));
|
Output
[22, 33, 44, 55, 66]
As we can see in the output, the total number of elements in the provided range is 5.