CODEWITHSUNDEEP
c
Gaurav Bhardwaj
Gaurav Bhardwaj

Reputation: 1

Perfect square with perfect digits within a range

What is the best way to get all the perfect squares with perfect digits between a range [a,b]? A perfect digit perfect square is the one with all its digits perfect squares. I did as follows

for j=a to b
    do if(checkPerfectSquare(j) && checkPerfectDigit(j))
        then ctr++
print ctr

int checkPerfectSquare(n)
{
if n<0
    return 0
root=round(sqrt(n))
return (n==root*root)
}

int checkPerfectDigit(n)
{
while n>0
    do rem=n%10
       n=n/10
    if(!checkPerfectSquare(rem))
        return 0
return 1
}

Upvotes: 0

Views: 791

Answers (2)

RISHABH DUBEY
RISHABH DUBEY

Reputation: 91

you can use

count=((floor(sqrt(b))-ceil(sqrt(a)))+1);

Upvotes: 0

starrify
starrify

Reputation: 14751

The pseudo code you provide seems correct -- except for typos like i and n in checkPerfectSquare. If your implementation gives unexpected results, please show your real code.

Okay here let us review your purpose: to select perfect square with perfect digits inside range [a,b]. Here is a simple idea:

  • To iterate through the range [a,b] and test each of the numbers. Actually this is exactly what you do. This gives correct answers of course, but please notice when a and b become large your problem would suffer from very low efficiency.

Notice that there're always fewer squares than all numbers in a range, we could do this:

  • To iterate through all perfect squares inside [a,b] and test whether they are made of perfect digits. How would this be? Inside the range of [10^(n-1), 10^n-1] (range of all n-digit numbers) there are merely about 10^(n/2) - 10^((n-1)/2) perfect squares! This is much smaller than the amount of numbers in this whole range, and as a result your program would run faster.

Well, if you're agreed with the above idea, you may write a better program. But wait, let's try reverse the order this time. Notice that there is actually only three perfect digits: 1 4 and 9, we may optimize the original idea like this:

  • To iterate through all numbers that are made of perfect digits (e.g. 1111111, 149149149, 111144449999) inside the range of [a,b], and test whether they are perfect squares. This would obviously run faster since there are 10^n numbers with n digits, while only 3^n with n perfect digits. This would be better than the idea above since 3^n = 9^(n/2) < 10^(n/2)

I'm not providing any pseudo or real code here for now. You may want to understand the ideas and try write some code first.

Upvotes: 1

Related Questions