Find the next multiple of N that is a perfect square number

Question

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?

Answer 1

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 \$.

Answer 2

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.

Answer 3

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.

Answer 4

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.