Is this number a perfect square?

-
When solving an algorithm problem, the size of the input will likely dictate the approach to be taken to solve it. For the following problem: "determine whether the number N is a perfect where N is <= 1,000,000. You can't use the SQRT operator", you can solve it by writing a simple O(N) loop. However, if the problem statement has N equals to this number:

165427932084831047046609078136342385692486778784193040575415275237601141991915477442845407673976779988232591513989058207150
467947523250038046743349535213521742642331376230769593309027187809744543689481194688348037467758678555486040607128113607782
083765614731180084729138856439466527641625533551140106381117226415600300034739904992269491478944475237827791509015498086952
540122244942342301906037349725404262930038509928927062527110279498414480102632727349285397856356384385317530337640402344225
257713111998890184844181150362794164888726083850881120857078821273038738588588961135056057777457454067942853805232017960397
050978282050240191161275882625340545212046053301789937251365351417557092804151385075718501245599282033350446561924254192091
369795348600116773792501535164938937988045822175670418981501598859205041941367469757259417288920323424307954390472898807024
169866780317563095596730093961453540231766035422026363095231945382670048030322566319763733609680577338280082965098102753044
938539186285154045953674169373914742467656886829914286825370454961565065712545956696734216204413321639282355852267935369390
44505866991230361009997941512327874199719123344

Then it is a different matter altogether. Such a problem should automatically trigger the most common time-complexities and their relationships:

O(1) < O(lgN) < O(lgN*lgN) < O(sqrt(N)) < O(N) < O(N*lgN) < O(N*N)

We know that O(N) won't work for the above input, hence we need to evaluate the other options less than O(N). O(sqrt(N)) won't work either as the square root of such a big number will remain a big, intractable number (intractable from a Big-O standpoint). This post will solve this problem using a O(lgN) algorithm. That would be suitable for our input size. I did not count how many digits there are in N, but let's suppose that it contains 1,000,000 digits (which it doesn't), in this case lg(10^1,000,000) ~= 4,000,000. Hence to solve the problem we'd need a for-loop with 4,000,000 iterations. Runs in a blink of an eye.

The most common O(lgN) algorithm is a binary search whereas on each iteration of the algorithm we cut the search space by half (remember that the notation "lgN" refers to the logarithm of N on base 2, whereas "logN" refers to the logarithm of N on base e, and logK(N) is the logarithm of N on base K). To solve the problem using binary search, we first find the lower and upper bounds for the search. We can do that by finding two perfect squares, one before N and one after N, relatively close together. That operation takes O(lgN). Next comes the binary search itself. We cut down the search by half at each step, and at the end either we'll find the square root of N, or the lower boundary will cross the upper boundary, we halt, and the number is not a perfect square. We make use of the BigInteger C# class for convenience. Here is the code:

        public static bool IsPerfectSquareBS(BigInteger n,
                                             ref BigInteger sqr)
        {
            sqr = -1;
            if (n < 0)
            {
                return false;
            }
            else if(n == 0 || n == 1)
            {
                sqr = n;
                return true;
            }
            //Find the lower and upper limits
            BigInteger lower = 1;
            BigInteger upper = 2;
            while(n < (lower * lower) || n > (upper * upper))
            {
                lower = upper;
                upper *= upper;
            }
            //Binary search
            while (lower + 1 < upper)
            {
                BigInteger mid = (lower + upper) / 2;
                BigInteger midSq = mid * mid;
                if (midSq == n)
                {
                    sqr = mid;
                    return true;
                }
                else if (midSq > n)
                {
                    upper = mid;
                }
                else
                {
                    lower = mid;
                }
            }
            return false;
        }
 
The answer to the original problem is yes, that number is a perfect square, and its square root is this one:

406728327123684670272930339169392162537633039383763635353442424384940383635112526326364646565768768797979808089897976867634
783749384937597485838392930832498748564857938430923028494856487594384039230394584584758456387483492830283497485684759394029
403586485783948932893028494758465873498320390238937583487329389282982981992939249349374938042343483948374837483749283934837
493894865757456464654545343432323131423535464657657687698798037328374364537327464646282983937454736319204644648364820298465
4732943747648374643837646362555515325337741359876723359467901178556591424572448536812

Comments

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

The Power Sum, a recursive problem by HackerRank

-
Image
Another one by HackerRank:  https://www.hackerrank.com/challenges/the-power-sum : Find the number of ways that a given integer,  , can be expressed as the sum of the   power of unique, natural numbers. Input Format The first line contains an integer  .  The second line contains an integer  . Constraints Output Format Output a single integer, the answer to the problem explained above. Sample Input 0 10 2 Sample Output 0 1 Explanation 0 If   and  , we need to find the number of ways that   can be represented as the sum of squares of unique numbers. This is the only way in which   can be expressed as the sum of unique squares. Sample Input 1 100 2 Sample Output 1 3 Explanation 1 Sample Input 2 100 3 Sample Output 2 1 Explanation 2  can be expressed as the sum of the cubes of  .  . There is no other way to express   as th
Read more