Count of Numbers in Range [L, R] having Sum of Digits of its Square Equal to Square of Sum of Digits

Approaches

We will take the brute force approach to solve this problem.

• We will iterate over all integers of the range [L, R].
• For each integer, we will check if it is having the sum of digits of its square equal to the square of the sum of digits.
• If the condition is satisfied, we will increment the count of such numbers.
• To find the sum of digits of a number we will define a separate function sumofDigits( ) that will use the modulo operator to find digits of the number.

Code

//C++ implementation

#include<bits/stdc++.h>
using namespace std;

//function for finding the sum of digits of a number
int sumofDigits(int n)
{
int s=0;
while(n!=0)
{
s+=n%10;
n=n/10;
}

return s;
}

//Counting  numbers in range [L, R] having sum of digits of its square equal to square of sum of digits
int count(int l,int r)
{
int ans=0;

for(int i=l;i<=r;i++)
{
//sum of digits of its square equal to square of sum of digits
if(sumofDigits(i*i)==sumofDigits(i)*sumofDigits(i))
{
ans++;
cout<<i<<" ";
}
}
cout<<endl;

return ans;
}

//driver code
int main()
{
int L=1,R=20;

cout<<"count of such numbers in the range ["<<l<<","<<r<<"] : "<<count(L,R);

}

Output

1 2 3 10 11 12 13 20
So, count of such numbers in the range [1,20] : 8

Complexity analysis

The Time Complexity of the above approach is O((R - L)*logR).

Space complexity is O(1).

FAQs

1. What is modulo operator?
   It is an arithmetic operator which is used to find the remainder of any integer division.
    
2. What is the left shift(<<) operator in C++?
   The left shift operator takes two integers and shifts bits of the first integer towards the left by no number of places equal to the second integer.
   E.g  (5<<1) = 10=(1010)2

Key Takeaways

This article covered how to count numbers in the range [L, R] having the sum of digits of its square equal to the square of the sum of digits.
Check out this problem - Subarray Sum Divisible By K

Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning!