Given a number, this program would find "all permutations of the pairs that add to squares" from 1 to number.
E.g: Given an input number of 16, one of the possible answers would be:
8:1:15:10:6:3:13:12:4:5:11:14:2:7:9:16
and its reverse.
Note that the function called hasIntegerRoot
has been commented out for a purpose. I would appreciate if reviewer would chose me to use hasIntegerRoot
over currently used List<Integer> squareList
.
I'm looking for code review, best practices, optimizations etc.
Verifying Complexity (where \$n\$ is the input number):
- Time: \$O(n!)\$
- Space: \$O(n!)\$
public final class PairSquare {
private PairSquare() {};
/**
* Given a number, this program would find "all permutations of the pairs that add to squares" from 1 to number"
*
* @param num The number upto which adjacent numbers should sum to a sqaure
* @return A List of all the lists/chains of integers such that adjacent numbers sum upto a square.
*/
public static List<List<Integer>> pairSquare (int num) {
if (num <= 0) throw new IllegalArgumentException("The input number " + num + " should be less than equal to zero.");
final List<List<Integer>> pairSquaresList = new ArrayList<List<Integer>>();
final List<Integer> squareList = squareList(num);
final LinkedHashSet<Integer> elements = new LinkedHashSet<Integer>();
for (int i = 1; i <= num; i++) {
elements.add(i);
getSqaureLists(i, num, elements, pairSquaresList, squareList);
elements.remove(i);
}
return pairSquaresList;
}
private static List<Integer> squareList(int num) {
int limit = num + (num - 1);
int n = 2;
final List<Integer> sqaureList = new ArrayList<Integer>();
int square;
while ((square = n * n) <= limit) {
sqaureList.add(square);
n++;
}
return sqaureList;
}
// private static boolean hasIntegerRoot(int x) {
// double root = Math.sqrt(x);
// return root == (int)root;
// }
private static void getSqaureLists(int currNum, int num, LinkedHashSet<Integer> elements, List<List<Integer>> pairSquareList, List<Integer> squareList) {
if (elements.size() == num) {
pairSquareList.add(new ArrayList<Integer>(elements));
return;
}
for (int i = 1; i <= num; i++) {
// a number has already been added in the list. deduping.
if (elements.contains(i)) continue;
// // checking if the adjacent numbers add up to a square of an int.
// if (hasIntegerRoot(i + currNum)) {
// elements.add(i);
// getSqaureLists(i, num, elements, pairSquareList, squareList);
// }
if (squareList.contains(i + currNum)) {
elements.add(i);
getSqaureLists(i, num, elements, pairSquareList, squareList);
}
elements.remove(i);
}
return;
}
public static void main(String[] args) {
List<Integer> list1 = Arrays.asList(8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16);
List<Integer> list2 = Arrays.asList(16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8);
List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();
listOfLists.add(list1);
listOfLists.add(list2);
Assert.assertEquals(listOfLists, pairSquare(16));
}
}