10
\$\begingroup\$

Given a number \$t\$, (\$1 \leq t \leq 1000\$) that represent testcases and \$t\$ numbers \$n\$ (\$1 \leq n \leq 10^9\$). Show the next multiple of \$n\$ that is a perfect square number.

Example of input:

5   
5 9 10 12 13

Example of output:

Case #1: 25
Case #2: 9
Case #3: 100
Case #4: 36
Case #5: 169

My solution iterates over all the next perfect squares of \$n\$ (using this formula \$ \left(\lfloor \sqrt{x} \rfloor + 1\right) ^ 2 \$ until it's a multiple of \$n\$.

#include <stdio.h>
#include <string.h>
#include <math.h>

unsigned long long myPow(unsigned long long x){
    return x*x;
}

int main(){

    unsigned int j;

    unsigned int t;
    scanf("%u",&t);

    for(j = 1; j <= t; j++){
        unsigned long long n;
        scanf("%llu",&n);
        double sqrtn = sqrt(n);
        if(sqrtn == (unsigned long long) sqrtn) //test if N is a perfect square
            printf("Case #%d: %llu\n",j,n);
        else{
            unsigned long long i = n;
            while((i = myPow(floor(sqrt(i))+1)) % n != 0);//find the next perfect square multipe of n
            printf("Case #%d: %llu\n",j,i);
        }
    }
}

This solution encounters "Time limit exceeded". Is there a faster way of finding the solution?

\$\endgroup\$
  • \$\begingroup\$ do you get the correct results when you run the code locally? \$\endgroup\$ – Malachi Apr 9 '15 at 15:16
  • 1
    \$\begingroup\$ Yep. It gives the correct answer. \$\endgroup\$ – user70000 Apr 9 '15 at 15:22
20
\$\begingroup\$

I'm afraid we need to use… math.

Take any square number and look at its prime factorization. For example, \$ 100 = 2^2·5^2 \$; \$ 144 = 2^4·3^2 \$; \$ 729 = 3^6 \$. The thing that's common to all of these examples is that the exponent of each prime in the factorization is even. And that's because if you take any number \$ n \$, with factorization $$ n = 2^a·3^b·5^c\dotsm $$ then its square is $$ n^2 = 2^{2a}·3^{2b}·5^{2c}\dotsm $$ where all the exponent are even.

So if you want to find the smallest multiple of \$ m \$ that's a square, then you can factorize $$ m = 2^a·3^b·5^c\dotsm $$ find the odd exponents among \$ a, b, c, \dotsc \$, and then multiply by the appropriate primes to make all the exponents even.

Let's take the number \$ 12 \$ as an example. First, factorize \$ 12 = 2^2·3^1 \$. Then note that \$ 3 \$ is raised to an odd exponent in the factorization. So we need to multiply by \$ 3 \$ to get \$ 2^2·3^2 = 36 \$ which is \$ 6^2 \$.

A bigger example: \$ 24696 \$. First, factorize \$ 24696 = 2^3·3^2·7^3 \$. Then note that both \$ 2 \$ and \$ 7 \$ are raised to odd exponents in the factorization. So we need to multiply by \$ 2·7 \$ to get \$ 2^4·3^2·7^4 = 345744 \$ which is \$ 588^2 \$.

\$\endgroup\$
  • 2
    \$\begingroup\$ I like this answer, but is it guaranteed to get the next multiple of n that is a square? I can see it will generate a square, but is it necessarily the smallest one? \$\endgroup\$ – Ryan Apr 9 '15 at 16:18
  • 4
    \$\begingroup\$ @Ryan: Proving that it is the smallest would make a good exercise. \$\endgroup\$ – Gareth Rees Apr 9 '15 at 16:23
  • \$\begingroup\$ I have to point out that integer factorization is not a simple stuff: en.wikipedia.org/wiki/Integer_factorization \$\endgroup\$ – Orace Apr 10 '15 at 12:23
  • 1
    \$\begingroup\$ @Orace: For the numbers in the OP's problem, which are no larger than \$ 10^9 \$, factorization by trial division will most likely be fine. This algorithm is easy to program. \$\endgroup\$ – Gareth Rees Apr 10 '15 at 13:55
  • \$\begingroup\$ I didn't even read the answer, I just upvoted it for the joke. \$\endgroup\$ – The Floating Brain Apr 11 '15 at 4:29
6
\$\begingroup\$

You are recomputing way too much in your code. Your general solution relies on iterating through powers starting at the first perfect square greater than \$\mathrm{n}\$.

  • There is no need to recompute square roots over and over as you do in the loop below:

    unsigned long long i = n;
    while((i = myPow(floor(sqrt(i))+1)) % n != 0);
    

    Instead you should choose a better loop index:

    for(unsigned int i = sqrtn+1; i*i % n != 0; i++);
    
  • myPow is not a very good name for your one function should you choose to keep it. It should be named mySquare instead.

More advanced stuff

  • I will also mention that there is a faster way to iterate through perfect squares and here is the proof:

    $$ (n+1)^2 = n^2 + 2n + 1 $$

    Let's substitute \$n+1\$, \$n+2\$, ..., \$n+k-1\$ in for \$n\$ in the above formula to see if we notice a pattern:

    $$ (n+2)^2 = (n+1)^2 + 2\cdot(n+1) + 1 = (n+1)^2 + 2n + 3$$ $$ (n+3)^2 = (n+2)^2 + 2\cdot(n+2) + 1 = (n+2)^2 + 2n + 5$$ $$ \vdots$$ $$ (n+k)^2 = (n+k-1)^2 + 2\cdot(n+k-1) + 1 = (n+k-1)^2 + 2n + 2k-1$$

    All we are doing is adding consecutive odd numbers to the previous perfect square to get the next perfect square in the sequence. Start from \$0\$ to get a feel for how it works: $$0,\> 1 = 0 + \textbf{1},\> 4 = 1 + \textbf{3},\> 9 = 4 + \textbf{5},\> 16 = 9 + \textbf{7},\> 25 = 16 + \textbf{9},\> ...$$

    This means we can use addition to iterate through perfect squares instead of multiplication. I highlight the method below:

    unsigned int usqrtn = sqrtn;
    unsigned int perfect_square = usqrtn * usqrtn;
    unsigned int step = 2*usqrtn+1;
    
    while(perfect_square % n != 0)
    {
        perfect_square += step;
        step += 2;
    }
    

    Keep in mind that this is still a brute force solution since we are iterating through every perfect square. It is just a smarter brute force solution.

  • As mentioned in the other answer you should factor the numbers instead since mathematical methods are typically faster than brute force.

\$\endgroup\$
  • \$\begingroup\$ Worst case when brute forcing is n=2*3*5*7*11*13*17*19=87297210, which has smallest square equal to n^2, meaning you are stepping through 87297209 squares before you find the answer. \$\endgroup\$ – Taemyr Apr 10 '15 at 10:44
  • 1
    \$\begingroup\$ @Taemyr Your calculation appears to be wrong but more importantly I think you are making some leaps in logic. The worst case will almost surely be the greatest number \$m\$ less than \$n\$ such that all of \$m\$'s prime factors are to the first power. While I have not confirmed that \$m\$ is not composed of contiguous primes, I highly doubt it would be. Also the only reason I can choose the greatest \$m\$ is because the number of squares in \$[\,m,\, m^2\,]\$ is \$m - \lceil{\sqrt{m}}\,\rceil\ + 1\$ which is monotonically non-decreasing for integers \$m \geq 0\$. \$\endgroup\$ – twohundredping Apr 10 '15 at 18:44
  • \$\begingroup\$ @Taemyr: Surely 999999937 is the worst case? \$\endgroup\$ – Gareth Rees Apr 11 '15 at 15:14
  • \$\begingroup\$ @GarethRees The worst case brute-force solution is actually \$m=999,999,998=2\cdot691\cdot723589\$ which requires iterating through \$999,968,376\$ perfect squares. Also the reason I said almost surely earlier is because I was not sure about the boundary cases. It can be shown however that if \$m\$ is of a form where all of its prime factors are not to the first power then at most we have to iterate through perfect squares in \$[\,m, \,\textrm{max}(4m,(m/4)\cdot m)]\$. We can use this to eliminate \$999,999,999\$ or we can explicitly factor it. \$\endgroup\$ – twohundredping Apr 12 '15 at 4:38
2
\$\begingroup\$

If you take any given number N, and factor it, you may or may not have squares in its root... although actually, you always do. And using these "square factors" are how bringing any number N "into square" (including determining all the multiples that will do so, and in any type of progression) is done:

If you "do not have a square in the root", then the smallest next square is to multiply by itself (because 1 is the only square number in the root and you always have that).

If you do have a square number in its root, then divide and/or multiply your number by these will yield the multiples that will bring N "into square". You can obtain progression by writing a rule that divides by the largest (to get the smallest multiple number), then the 2nd largest, etc..... on through multiplying by the smallest, and up through multiplying by the largest.

For example, 20: 20 roots into 5, 2, 2, 1 and 4 is a square number. So 20/4 = 5 and 20*4 = 80, which when multiplied by 20 yields 100 and 1600. The progression of multiples for 20 that will yield square numbers are 5, 20, 80.

Another example, 36: 36 roots into 3, 3, 2, 2, 1 So 36/9 = 4, 36/4 = 9, 36*4 = 144, and 36*9 = 324. So multiples for 36 that will result in square numbers once multiplied are 4, 9, 36, 144, 324 with resultant square numbers being 144, 324, 1296, 5184, 11664. Important note: using the numbers own square root (in cases where the original N is square, as with 36) does not work (36/6 = 6 and 36*6 does NOT yield a square number and this is because 6 in itself is not a square number).

I have a website where I came across the need to find such multiples for 6808, and it held true with the square in the root being 4. So multiples were 1702, 6808, and 27232. Brute force in Excel did verify that 1702 was indeed the smallest multiple to bring 6808 into square (result = 11587216, square root of which is 3404).

In a nutshell, it is an extension of the fact that any square number multiplied by any square number will yield a square number. But by using the "root factors that are square" to derive your multiples instead, you expand the ability into being able to convert ANY number into a square, through all of its possible progressions --- without brute force.

\$\endgroup\$
1
\$\begingroup\$

A simple solution would be

  1. Keep dividing the number by the smallest prime factor.
  2. Push the factor to the stack if it is not equal to top. Pop stack top if stack top equals the current prime factor.
  3. Whatever remains in the stack should be multiplied with the original number.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy