Find an integer that its squared value has a certain pattern

Question

I want to find an integer called result, where its squared value (result^2) has a pattern of 1_2_3_4_5_6_7_8_9_0 (with _ being digits). My approach is, find all numbers with such pattern and find the number with its square root being an integer:

 #include <cmath>
#include <string>

using std::string;

int main(){

    std::string candidate;

    long result; 

    long maxPosibleSq = 1929394959697989990;
    long minPosibleSq = 1020304050607080900;


    for (long i=minPosibleSq; i<=maxPosibleSq; i+=10 /*last digit is always 0*/){
        if (sqrt(i)==floor(sqrt(i))){
            candidate = std::to_string(i);
            if (candidate[2]=='2' && candidate[4]=='3' && candidate[6]=='4' && candidate[8]=='5' && candidate[10]=='6'
            && candidate[12]=='7' && candidate[14]=='8' && candidate[16]=='9'){
                result=std::stol(candidate);
                break;
            }
        }
    }

    return 0;
}

The compiler gave me warnings on potential overflows because maxPosibleSq and minPosibleSqare too big. Are there any better and faster ways to do it?

As a general subject area if you are doing this sort of thing, see [Arbitrary-Precision Arithmetic](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic). Or see this answer about the [square root of a 100 digit number](http://stackoverflow.com/a/15998678), for instance. — HostileFork says dont trust SE, Feb 20 '16 at 07:16
I did not understand well. the digits should be unique is to say: 1323334353637383930 OR 1727374757677787970 and not 1122334455667788990 ??? — , Feb 21 '16 at 14:41
@AtmaneELBOUACHRI all of the mentioned can be possible candidates — Dylan Czenski, Feb 24 '16 at 20:03

Adi Levin · Accepted Answer · 2016-02-20T07:27:41.987

Another way to do this is to traverse a range of integer numbers that might be the square root of 1_2_3_4_5_6_7_8_9_0. The range is between sqrt(10203040506070809) and sqrt(19293949596979899). There are approximately 380 million such numbers. For each number, calculate its square root, and see if it fits the pattern

Even better, you can step through this range at steps of 10, because the last digit of your answer has to be zero, since its square ends with a zero. Therefore, you have only about 38 million numbers to go through.

And to avoid overflow errors, use unsigned long long which will give you 64 bit integers. The maximum number you can represent is 18446744073709551615 which has 20 digits.

We know that the answer must be 9 digits. Start with 1 and end with 0. So we only need 3.8 million number to go — invisal, Feb 20 '16 at 08:14

Find an integer that its squared value has a certain pattern

1 Answers1