7
\$\begingroup\$

I am writing a program that allows me to find all possible pairs of square numbers including duplicates. We can also assume the array elements to be of positive integers only. 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);

}
\$\endgroup\$
  • \$\begingroup\$ Are the duplicates in the result intentional? \$\endgroup\$ – Alexander Jul 18 at 19:11
  • \$\begingroup\$ Yes, they are intentional. I've updated my post. \$\endgroup\$ – JanB Jul 18 at 20:04
8
\$\begingroup\$

Avoid string addition

String addition is not good for building up strings from many pieces 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]) {
            ...

Pairs need distinct indices

If your input contains a single 0 or 1, it will mistakenly report that it has found a pair, since 0 == 0*0 and 1 == 1*1. You can protect against this by adding i != j && to your test.

If the input contains two 0's (or two 1's), your algorithm will emit 4 pairs: [first,first], [first,second], [second,first], and [second,second]. Adding the i != j guard will eliminate the first and last of those pairs, but it will still declare two pairs: [first,second], [second,first] since first² = second and first = second² would both be true. You'd have to weight in on whether this would be two distinct pairs or not.

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, an 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ A binary search requires a sorted list. If you are willing to sort your list, \$O(n \log n)\$, then you are better off moving two index (i & j) through the list from one end to the other. If arr[i] > arr[j]*arr[j], increase j. If arr[i] < arr[j]*arr[j], then increase i. Note: you'll need a different approach to handle negative numbers. \$\endgroup\$ – AJNeufeld Jul 17 at 21:30
  • \$\begingroup\$ However, if i were to sort ( O(n^2) ) and then uses binary search ( O(nlogn) ), the performance of the new algorithm will be slower than what my code ( O(n^2) ) is doing now right? \$\endgroup\$ – JanB Jul 17 at 21:45
  • \$\begingroup\$ Arrays.sort(int[]) is \$O(n \log n)\$, not \$O(n^2)\$. If you sort, and the loop over every index (\$O(n)\$), and did a binary search (\$O(\log n)\$), you'd end up with \$O(n \log n)\$. But sort & n binary searches is \$O(n \log n + n \log n)\$ where as sort & a single pass scan is \$O(n \log n + n)\$, so slightly faster. \$\endgroup\$ – AJNeufeld Jul 17 at 21:49
  • \$\begingroup\$ Alright, thank you so much for your help. \$\endgroup\$ – JanB Jul 17 at 21:52
  • 1
    \$\begingroup\$ @JoachimRohde Interesting article. But original JEP doesn't state that anything will be changed regarding loops. Btw, found this interesting repo: github.com/mtumilowicz/java9-string-concat (didn't tested it though) \$\endgroup\$ – Flame239 Jul 18 at 12:00
5
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ The set construction cost is O(n log n) docs.microsoft.com: This constructor is an O(n) operation. If the output order doesn't mattergood catch, I might have missed that one. … and you aren't interested in duplicates big if, judging from the example output of three pairs given one instance of 5 and three instances of its square. \$\endgroup\$ – greybeard Jul 18 at 5:06
  • \$\begingroup\$ You're right about the set construction being O(n), I was thinking of persistent data structures rather than hash tables -- old habits. If you need duplicates, you can use this one-liner to calculate frequencies: var freqs = arr.OrderBy(x => x).GroupBy(x => x).ToDictionary(x => x.Key, x => x.Count()); \$\endgroup\$ – Rafe Jul 18 at 6:26
  • \$\begingroup\$ Corresponding Java code could look like this. \$\endgroup\$ – Eric Duminil Jul 18 at 7:49
  • \$\begingroup\$ Thank you all for the respond. Just wondering how do you guys calculate the run time complexity of in-built collections such as HashSet? Do we just take it from the documentation manual or are we able to calculate it by analysing the algorithm just like a nested for loop. \$\endgroup\$ – JanB Jul 18 at 8:49
  • \$\begingroup\$ @JanB generally, you dont. You know the complexity of the ADT which language-independent (found on wiki) and hope any widely-spread implementation is the optimal one. \$\endgroup\$ – wondra Jul 18 at 12:10
2
\$\begingroup\$

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 to 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 that root
    (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 (order on first lookup as a root), increasing additional space to O(n))
\$\endgroup\$
  • \$\begingroup\$ Thank you for your advice. However, may i ask how does establishing a count reduces run time? \$\endgroup\$ – JanB Jul 18 at 9:02
  • \$\begingroup\$ When "in phase 3" you find a root of some square, you don't need to consult the input array to output the appropriate number of pairs if you got that count. (You can do similar (and more, see if order of negative and positive roots mattered) with a set of tuples (Map<Integer, List<Integer>>).) \$\endgroup\$ – greybeard Jul 18 at 19:55
  • \$\begingroup\$ Ahh makes sense.. Thank you for the reply!! \$\endgroup\$ – JanB Jul 18 at 20:11
  • \$\begingroup\$ (Coding this in Java looked, hm, verbose. I can see where [AJNeufeld] may have got the idea to use streams.) \$\endgroup\$ – greybeard Jul 19 at 4:39
1
\$\begingroup\$

Consider building a different data structure.

Map<Integer, Integer> valueCounts = new HashMap<>();
for (int element : arr) {
    Integer count = valueCounts.getOrDefault(element, 0);
    valueCounts.put(element, count + 1);
}

Now we know how many times each element appears in the data. So we can just

Map<Integer, Integer> results = new HashMap<>();
for (Map.Entry<Integer, Integer> valueCount : valueCounts.entrySet()) {
    int square = valueCount.getKey() * valueCount.getKey();
    int count = valueCounts.getOrDefault(square, 0);

    if (count > 0) {
        results.put(valueCount.getKey(), valueCount.getValue() * count);
    }
}

This tells us how many pairs there are without actually counting them. It only counts the elements (in the first block).

Your original was \$\mathcal{O}(n^2)\$. This version is \$\mathcal{O}(n)\$. You were using nested loops, where this uses sequential loops.

Note: I haven't tested this so beware of typos, etc.

I separated generation from display. You'll still have to generate the display string. If it seems like we're missing part of the pair, remember that the second part is always the square of the first part. You can just generate it as you go.

\$\endgroup\$
0
\$\begingroup\$

My answer is additive to the others; I'm not going to repeat points already made.

1. Nitpick: prefer int[] arr over int arr[]

The "arrayness" ([]) has more to do with the type than it does the variable name, so it's better to keep them together. Not to appeal to authority, but Google's style guide also suggests this.

2. Avoid "for" loops where "for-each" loops are applicable.

You never really need the indices i and j, aside from using them to get the elements. Just avoid them altogether:

for (int a : arr) {
    for (int b : arr) {
        if (Math.sqrt(a) == b) {
            s += a + "," + b + " ";
        }
    }
}

Even if a for-each loop wasn't available (e.g. in C), I would still recommend extracting repeated terms (arr[i], arr[j]) to a variable.

3. Don't intermix computation of a result, and the printing of the result

I would advise against this cross-over of computing and printing that you're doing.

Perhaps you want to use this list as an input to some other process. Parsing the string back would be both inconvenient and inefficient. It's better to make systems that shuttle around machine-usable values (e.g. a list of numbers) as much as possible, and only formatting and printing them as the last possible moment.

Here's a first approximation:

import java.util.List;
import java.util.ArrayList;

class Untitled {
    public static void main(String[] args) {
        int arr[] = {5,25,3,25,4,2,25};

        List<Integer> discoveredRoots = new ArrayList<>();
        for (int a : arr) {
            for (int b : arr) {
                if (Math.sqrt(a) == b) {
                    discoveredRoots.add(b);
                }
            }
        }

        String s = "";
        for (int root : discoveredRoots) {
            int perfectSquare = root * root;
            s += root + "," + perfectSquare + " ";
        }
        System.out.println(s);
    }
}

4. Split off distinct chunks of code

Now we have two distinct chunks of our code within the main function. These are clearly two new functions, just waiting to get out:

class Untitled {
    public static void main(String[] args) {
        int[] input = {5,25,3,25,4,2,25};

        List<Integer> discoveredRoots = findPerfectSquarePairs(input);
        String formattedResult = formatPerfectSquarePairs(discoveredRoots);
        System.out.println(formattedResult);
    }


    // Returns a stream of factors whose squares (which are perfect squares)
    // were found in `input`.
    static List<Integer> findPerfectSquarePairs(int[] input) {
        List<Integer> discoveredRoots = new ArrayList<>();

        for (int a : input) {
            for (int b : input) {
                if (Math.sqrt(a) == b) {
                    discoveredRoots.add(b);
                }
            }
        }

        return discoveredRoots;
    }

    static String formatPerfectSquarePairs(List<Integer> discoveredRoots) {
        String s = "";

        for (Integer root : discoveredRoots) {
            int perfectSquare = root * root;
            s += root + "," + perfectSquare + " ";
        }

        return s;
    }
}

These functions have the added benefit of being pure. They don't do anything besides process over their parameters, and return a value (e.g. they don't print anything directly). * The lack of side-effects make these methods trivial to unit unit test. Just provide some hard-coded parameters, and assert that their equality to some hard-coded results. * Their separation make isolation trivial. You can test printing without processing, and processing without printing.

5. Optimize the internals of findPerfectSquarePairs and formatPerfectSquarePairs.

Now that we've "discovered" these two functions, we can improve each component separately. We're able to lean on unit tests to ensure we didn't break anything.

First, we can use a Set to remember which numbers we've seen, without having to do a O(input.length * 2) search over every possible pair of numbers. We don't even have to put every number in the set, only those which are perfect squares.

    /*
    import static java.lang.Math.pow;
    import static java.lang.Math.sqrt;
    import static java.lang.Math.round;
    */

    static boolean isPerfectSquare(int i) {
        if (i < 0) return false; // negative numbers can't be perfect squares

        double root = sqrt(i);
        double squared = pow(round(root), 2);
        return round(squared) == i;
    }
    static List<Integer> findPerfectSquarePairs(int[] input) {
        Set<Integer> uniqueNumbers = new HashSet<>();
        for (int a: input) {
            if (isPerfectSquare(a)) uniqueNumbers.add(a);
        }

        List<Integer> discoveredRoots = new ArrayList();

        for (int a : uniqueNumbers) {
            int perfectSquare = a * a;
            if (uniqueNumbers.contains(perfectSquare)) {
                discoveredRoots.add(a);
            }
        }

        return new ArrayList(discoveredRoots);
    }

All of these loops are just a stream screaming to get out. Let's do that:

    /*
    import static java.lang.Math.pow;
    import static java.lang.Math.sqrt;
    import static java.lang.Math.round;

    import static java.util.stream.Collectors.toSet;
    import static java.util.stream.Collectors.toList;
    */

    static List<Integer> findPerfectSquarePairs(int[] input) {
        Set<Integer> perfectSquares = Arrays.stream(input)
            .filter(Untitled::isPerfectSquare)
            .boxed()
            .collect(toSet());

        List<Integer> discoveredRoots = perfectSquares.stream()
                    .filter (root -> {
                        int perfectSquare = root * root;
                        return perfectSquares.contains(perfectSquare);
                    })
                    .collect(toList());

        return discoveredRoots;
    }

Next we can turn our attention to formatPerfectSquarePairs. It too could be simplified with a stream:

    static String formatPerfectSquarePairs(List<Integer> discoveredRoots) {
        return discoveredRoots.stream()
            .map(root -> {
                int perfectSquare = root * root;
                return root + "," + perfectSquare;
            })
            .collect(joining(" "));
    }

6. Redesign the interaction of findPerfectSquarePairs and formatPerfectSquarePairs

At this point, we can realize that both of these methods use streams internally, but don't communicate to each other using streams. findPerfectSquarePairs unnecessarily collects results into a List<Integer>, only for formatPerfectSquarePairs to stream() its elements. This is unnecessary.

Returning a Stream<Integer> would use less memory (there's no need to concurrently store all discoveredRoots in memory), and would be more flexible. If consumers want a List<Integer>, they can .collect(toList()) it themselves. But now we've given them the ability to iterate over the stream, to reduce it, map it, etc.

    static Stream<Integer> findPerfectSquarePairs(int[] input) {
        Set<Integer> perfectSquares = Arrays.stream(input)
            .filter(Untitled::isPerfectSquare)
            .boxed()
            .collect(toSet());

        return perfectSquares.stream()
            .filter (root -> {
                int perfectSquare = root * root;
                return perfectSquares.contains(perfectSquare);
            });
    }

    static String formatPerfectSquarePairs(Stream<Integer> discoveredRoots) {
        return discoveredRoots
            .map(root -> {
                int perfectSquare = root * root;
                return root + "," + perfectSquare;
            })
            .collect(joining(" "));
    }

7. Fix the formatting of the output

...to match your desired [5,25],[5,25],[2,4],[5,25] style:

    static String formatPerfectSquarePairs(Stream<Integer> discoveredRoots) {
        return discoveredRoots
            .map(root -> {
                int perfectSquare = root * root;
                return root + "," + perfectSquare;
            })
            .map(s -> "[" + s + "]")
            .collect(joining(","));
    }

Final result

import java.util.Set;
import java.util.Arrays;

import java.util.stream.Stream;

import static java.lang.Math.pow;
import static java.lang.Math.sqrt;
import static java.lang.Math.round;

import static java.util.stream.Collectors.toSet;
import static java.util.stream.Collectors.joining;

class Untitled {
    public static void main(String[] args) {
        int[] input = {5,25,3,25,4,2,25};

        Stream<Integer> discoveredRoots = findPerfectSquarePairs(input);
        String formattedResult = formatPerfectSquarePairs(discoveredRoots);
        System.out.println(formattedResult);
    }

    static boolean isPerfectSquare(int i) {
        if (i < 0) return false; // negative numbers can be perfect squares

        double root = sqrt(i);
        double squared = pow(round(root), 2);
        return round(squared) == i;
    }


    static Stream<Integer> findPerfectSquarePairs(int[] input) {
        Set<Integer> perfectSquares = Arrays.stream(input)
            .filter(Untitled::isPerfectSquare)
            .boxed()
            .collect(toSet());

        return perfectSquares.stream()
            .filter (root -> {
                int perfectSquare = root * root;
                return perfectSquares.contains(perfectSquare);
            });
    }

    static String formatPerfectSquarePairs(Stream<Integer> discoveredRoots) {
        return discoveredRoots
            .map(root -> {
                int perfectSquare = root * root;
                return root + "," + perfectSquare;
            })
            .map(s -> "[" + s + "]")
            .collect(joining(","));
    }
}
```
\$\endgroup\$
  • \$\begingroup\$ Can you try and doc-comment what it is your findPerfectSquarePairs() returns? I end up with something like stream of perfect squares from the input the perfect square of which appeared in the input, too, and the output looks the type. \$\endgroup\$ – greybeard Jul 19 at 4:13
  • \$\begingroup\$ @greybeard I couldn't find a good name for it. Ideally, I would have like to return tuple of two integers ("root" and "square"). I could make a POJO class to store them, but it's just way too verbose, so I didn't bother. Instead, the method only returns the roots, and any consumer can calculate the perfect square for themselves by just squaring it \$\endgroup\$ – Alexander Jul 19 at 4:51
  • \$\begingroup\$ (Funny coincidence lamenting verbosity) The problem is not just the name or documenting the return value: it is the return value, too, and the way it is generated. (Did you try running it?) (Why on earth return (ordered) tuples where one element can be derived from the other? That said, in Java you can still use an array for a homogeneous tuple - pity the notation is clumsy but in initialisers.) \$\endgroup\$ – greybeard Jul 19 at 5:51
  • \$\begingroup\$ I did run it, yes. What's the issue, I'm not catching on. "That said, in Java you can still use an array for a homogeneous tuple - pity the notation is clumsy but in initialisers." Yeah, I was tempted to do it, but it's really quite ugly \$\endgroup\$ – Alexander Jul 19 at 6:10
  • \$\begingroup\$ What output do you get for the array from the question? I get an empty output; more ([4,16],[25,625]) if I add , 16, 625 to the input. \$\endgroup\$ – greybeard Jul 19 at 17:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.