CODEWITHSUNDEEP
c#algorithm
Ramzes
Ramzes

Reputation: 13

Codewar task. How to find simple square numbers by the condition?

I tried to solve this problem on Codewar, but I don`t understand how to find exceptions.

In this Kata, you will be given a number n (n > 0) and your task will be to return the smallest square number N (N > 0) such that n + N is also a perfect square. If there is no answer, return -1 (nil in Clojure, Nothing in Haskell).

Here code that I wrote:

using System;

public class SqNum
{
    public static long solve(long n){  
       int N = 1;
            long lTemp = n;
            double sum, result;
            bool isSqare;
            while(true)
            {
                sum = lTemp + N;
                result = Math.Sqrt(sum);
                isSqare = result % 1 == 0;
                if(n == 4)
                {
                  return -1;
                }

                if(isSqare == true)
                {
                    return Convert.ToInt32(result);
                }
                N++;
            }
            return -1;
      }
}

Upvotes: 0

Views: 1453

Answers (1)

MBo
MBo

Reputation: 80177

If N (square) is p^2, and n+N=r^2, you can write

n + p^2 = r^2
n = r^2 - p^2
n = (r - p) * (r + p)

If we represent n as product of pair of divisors:

n = a * b     // let a<=b
a * b = (r - p) * (r + p)

We have system

r - p = a
r + p = b

and

p = (b - a) / 2

When p is the smallest? In the case of maximal close factors b and a. So we can try to calculate divisors starting from square root of n. Also note that a and b should have the same parity (to make p integer)

Pseudocode:

int N = -1;
for (int a = Math.Ceiling(Math.Sqrt(n)) - 1; a > 0; a--) {
   if (n % a == 0) {
      int bma = n / a - a;
      if (bma % 2 == 0) {
         int p = bma / 2;
         int N = p * p;
         break;
      }
   }
}

Examples: 

n = 16
first divisor below sqrt(16) a = 2, b=8
p = 3, 16 + 9 = 25

n = 13
first divisor below sqrt(13) a = 1, b=13
p = 6, 13 + 36 = 49

n = 72
first divisor below sqrt(72) is a = 8, b= 9 - but distinct parity!
so the next suitable pair is a = 6, b = 12
p = 3, 72 + 9 = 81

Upvotes: 1

Related Questions