Pythagorean triplets

Question

This code is about finding Pythagorean triplets. I take a number as input, and find from 1 to that number, how many Pythagorean triplets exist.

Are there ways this can be optimized? It takes a lot of time, but actually doesn't only provide the output for no > 10000

import java.util.*;
import java.io.*;

public class Solution
{

BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
HashMap<Integer,Set<Set<Integer>>> mymap=new HashMap<Integer,Set<Set<Integer>>>();
public static void main(String args[])
{
    Solution s=new Solution();
    try
    {
        int t=Integer.parseInt(s.in.readLine());
        for(int i=0;i<t;i++)
            {
                int no=Integer.parseInt(s.in.readLine());
                s.findAllPythogoreanTriplets(no);
            }
    }
    catch(Exception e)
    {
        e.printStackTrace();
    }



}
public void findAllPythogoreanTriplets(int no) {


    if(mymap.containsKey(new Integer(no)))
        System.out.println(mymap.get(no).size());
    else
    {
    int [] unsortedData=new int[no];
    for(int i=0;i<no;i++)
        unsortedData[i]=i+1;
// O(n) - Square all the elements in the array
for (int i = 0; i < unsortedData.length; i++)
    unsortedData[i] *= unsortedData[i];

// O(n logn) - Sort
int [] sortedSquareData = unsortedData;

// O(n2)
Set<Set<Integer>> triplets = new HashSet<Set<Integer>>();

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

    Set<Set<Integer>> pairs = findAllPairsThatSumToAConstant(sortedSquareData, sortedSquareData[i]);

    for (Set<Integer> pair : pairs) {
        Set<Integer> triplet = new HashSet<Integer>();
        for (Integer n : pair) {
            triplet.add((int)Math.sqrt(n));
        }
        triplet.add((int)Math.sqrt(sortedSquareData[i])); // adding the third element to the pair to make it a triplet
        triplets.add(triplet);
    }
}
mymap.put(no,triplets);
System.out.println(triplets.size());
}

}


public Set<Set<Integer>> findAllPairsThatSumToAConstant(int [] sortedData, int constant) {

// O(n)
Set<Set<Integer>> pairs = new HashSet<Set<Integer>>();
int p1 = 0; // pointing to the first element
int p2 = sortedData.length - 1; // pointing to the last element
while (p1 < p2) {
    int pointersSum = sortedData[p1] + sortedData[p2];
    if (pointersSum > constant)
        p2--;
    else if (pointersSum < constant)
        p1++;
    else {
        Set<Integer> set = new HashSet<Integer>();
        set.add(sortedData[p1]);
        set.add(sortedData[p2]);
        pairs.add(set);
        p1++;
        p2--;
    }
}
return pairs;
 }
 }

Answer 1

I will not start about optimatization but I'll do first a review so you could write better code and can post it again in a new question.

Take a look at this code in the question.
That question is a vey nice example of understandable coding.

No logic in static void main (String args[])

Your main method may only do :

• Init of your initials vars.

• Call your class for solution.

• Print out the result.

I see multiple times call to your Solution class.
This is possible when you want to ask multiple cases, but al least in the for-loop there must be a printout of the result.

Class should return solution of your problem.

Your method public void findAllPythogoreanTriplets(int no) should return the solution of the problem.
Your method is void so you can never output your solution.(keep in mind previous comment). The method should be :

public set<PythogoreanTriplet> findAllPythogoreanTriplets (Set<Integer>)

I should create a basic Pojo class for a triplet.
The Set<Integer> as parameter is up to discussion, you could use a List, Iterable, Collection or just an array.

Naming of variables, methods and class.

What a name is Solution for a class?
How do you know what it does?
What about PythagoreanTripletsFinder as class name?

Same for vars :

for(int i=0;i<t;i++)

i you could define as counter, t you could define as maxLinesToRead.

Formatting of code

If you use a more intelligent IDE you can do an autoformat of code.
This increase the readability of the code.
For netbeans : alt + shift + F
For eclipse : Ctrl + Shift + F

Smaller methods equals lesser complexity

You have 2 methods for the whole problem solution.
Complexity is very high for each method.

Your comments are already set on a nice place to extract that little piece of code to an extra method.
Also same with if - else.
The code in the braces in the if you could extract to a method (of course when its more then one line), the same for the else condition.

Always use braces

for(int i=0;i<no;i++)
    unsortedData[i]=i+1;

should be :

for(int i=0;i<no;i++) {
    unsortedData[i]=i+1;
}

It's clearder to see what you want to do with the for.
On the other hand searching a bug is also faster when you always set braces.

Scoping global variables

BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
HashMap<Integer,Set<Set<Integer>>> mymap=new HashMap<Integer,Set<Set<Integer>>>();

They are now package private.
I don't have something against package private scope but always make your global variables private and make them accesible outside the class with getters and/or setters.
No one will ask if it is your intention when you make a method package private cause almost nobody makes that fault, while on the other hand a lot of people forget to scope the global variables.

so it should be :

private BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
private HashMap<Integer,Set<Set<Integer>>> mymap=new HashMap<Integer,Set<Set<Integer>>>();

In your example I don't think you need getters/setters for outside the class.

Answer 2

You can use Euclid's formula to find the triplets. This formula says that the triplet (a, b, c) can be generated by using two integer m and n, where a = 2mn, b = m^2 - n^2, and c = m^2 + n^2. For example,

int max = 1000000;
for (int m = 1; m*m <= max; m++) {
  for (int n = 1; n <= m && (m*m) + (n*n) <= max; n++) {
    int a = 2*m*n;
    int b = m*m - n*n;
    int c = m*m + n*n;
    // print a, b, and c
  }
}

The algorithm above produces duplicate triplets (e.g., (3, 4, 5) and (4, 3, 5)). But, it we can easily add a check to prevent this problem. I will leave it to you to figure out.