Mdthbs

I am writing a program that allows me to find all possible pairs of square numbers.
e.g an array of {5,25,3,25,4,2,25} will return [5,25],[5,25],[2,4],[5,25]
since 25 is square of 5

currently, i am using a nested for loop to find the squares. I'm just wondering if there is a better way to do this?

import java.lang.Math.*;



public static void main(String args[])

{

    int arr[] = {5,25,3,25,4,2,25};

    String s = "";



    for(int i =0; i < arr.length;i++)

    {



        for(int j = 0;j < arr.length;j++)

        {

            if(Math.sqrt(arr[i]) == arr[j])

            {

                s += arr[j] + "," + arr[i] + " ";

            }

        }



    }



    System.out.println(s);



}

Avoid string addition

String addition is not good for building up strings from many pieces ... especially inside of loops. You should use StringBuilder instead.

StringBuilder sb = new StringBuilder();



// ... omitted ...



        sb.append(arr[j]).append(',').append(arr[j]).append(' ');



// ... omitted ...



String s = sb.toString();

System.out.println(s);

Avoid square-roots

Checking $sqrt x == y$ is ... dangerous.

• The results of the square-root are a float-point number, and may not exactly equal your integer value.


• If you have a negative number in your list, Math.sqrt() will raise an exception, yet { -5, 25 } is a valid pair.

Testing x == y*y is safer, as long as there is no danger of y*y overflowing.

Avoid repeated calculations

for(int i =0; i < arr.length;i++) {

    for(int j = 0;j < arr.length;j++) {

        if(Math.sqrt(arr[i]) == arr[j]) {

            ...

In the inner-loop, i is constant. Yet you are computing Math.sqrt(arr[i]) every time through the loop. The value should not be changing, so you could compute it once, outside of the inner loop.

for(int i =0; i < arr.length;i++) {

    double sqrt_arr_i = Math.sqrt(arr[i]);

    for(int j = 0;j < arr.length;j++) {

        if(sqrt_arr_i == arr[j]) {

            ...

Formatting

Consistent and liberal use of white space is always recommended. Add white space after every semicolon inside of for(...), on both sides of operators (i = 0 not i =0), and after every comma in {5,25,3,25,4,2,25}.

With the above recommendations, your function body would become:

int arr[] = { 5, 25, 3, 25, 4, 2, 25 };

StringBuilder sb = new StringBuilder();



for(int i = 0; i < arr.length; i++)

{

    for(int j = 0; j < arr.length; j++)

    {

        if(arr[i] == arr[j] * arr[j])

        {

            sb.append(arr[j]).append(',').append(arr[i]).append(" ");

        }

    }

}



String s = sb.toString();

System.out.println(s);

Additional considerations

You have a trailing space in your resulting string. There are several tricks you can use to remove it. However, and interesting alternative is to use StringJoiner:

StringJoiner sj = new StringJoiner(" ");



// ... omitted ...



        sj.add(arr[j] + "," + arr[j]);



// ... omitted ...



String s = sj.toString();

System.out.println(s);

When StringJoiner adds the second and successive strings, it automatically adds the delimiter specified in the constructor.

rather than writing all the loops by hand, can I suggest you use a different data structure? (I'm a C# programmer, hopefully my code will be easy to translate into Java.)

If the output order doesn't matter and you aren't interested in duplicates, you could get away with something like this:

var arr = new [] {5, 25, 3, 25, 4, 2, 25};

var set = new HashSet<int>(arr);

var roots = arr.Where(x => set.Contains(x * x));

foreach (var root in roots) Console.WriteLine($"{root}, {root * root}");

The set construction cost is O(n log n), which dominates the running time here (compare this to the nested loops approach which will costs O(n^2)). Also, as @AJNeufeld points out, you definitely want to avoid calculating square roots when you can get away with simple integer multiplication.

From eyeballing it, your code doesn't quite produce the format shown after will return (pairs separated by "," instead of "], [".

An alternative to building a String and then printing it is printing its parts immediately -

I'd define a method like long squares(Appendable destination):

works with both StringBuilder and OutputStream. (Returning the count of pairs.)

Just a sketch how to reduce run time machine operations:

• determine max as the maximum input value (terminate with no pairs if negative), and maxRoot = floor(sqrt(max+1))


• establish the count of every number from -maxRoot to maxRoot
  
  (assuming [5, 25] was be reported six times if another five was in the example input -
  
  specifying required output by example is hard, by a single example sub-optimal)


• for every non-negative input number that has integer roots in the input, report as many pairs for each of its roots as there are occurrences of it
  
  (assuming the order didn't matter between, say, [2,4] and [-2,4].
  If that mattered, too, you'd need to keep positions instead of counts, increasing additional space to O(n))