Skip to content

Instantly share code, notes, and snippets.

@madhur madhur/Problem3.java
Created Nov 18, 2017

Embed
What would you like to do?
import java.util.*;
public class Problem3 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int testCases = scan.nextInt();
List<Integer> numbers = new ArrayList<>();
for ( int i =1; i<=testCases; ++i) {
numbers.add(scan.nextInt());
}
for (Integer number : numbers) {
findPairs(number);
}
}
private static void findPairs(Integer number) {
HashSet<Pair> pairs = new HashSet<>();
for(int i=10;i <=number; ++i) {
int a = i;
//System.out.println("Trying " + a);
ArrayList<Integer> digitsArray =getDigitsArray(a);
for(int j =0; j< digitsArray.size(); ++j) {
List<List<Integer>> permutations = listPermutations(digitsArray);
for(List<Integer> list: permutations) {
for (int k =0; k<list.size(); ++k) {
ArrayList<Integer> copyArray = new ArrayList<Integer>(list);
copyArray.remove(k);
int b = convertToNumber(copyArray);
if(a + b == number && a != b) {
// System.out.println("Found pair for: " + a);
pairs.add(new Pair(a,b));
}
}
}
}
}
System.out.println(pairs.size() + " pairs found");
for(Pair pair: pairs) {
System.out.println(pair);
}
}
private static Integer convertToNumber(ArrayList<Integer> digits) {
Integer number = 0;
for (int digit : digits) {
number *= 10;
number += digit;
}
//System.out.println("Array is " + digits + "Number is: " + number);
return number;
}
public static List<List<Integer>> listPermutations(List<Integer> list) {
if (list.size() == 0) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
result.add(new ArrayList<Integer>());
return result;
}
List<List<Integer>> returnMe = new ArrayList<List<Integer>>();
Integer firstElement = list.remove(0);
List<List<Integer>> recursiveReturn = listPermutations(list);
for (List<Integer> li : recursiveReturn) {
for (int index = 0; index <= li.size(); index++) {
List<Integer> temp = new ArrayList<Integer>(li);
temp.add(index, firstElement);
returnMe.add(temp);
}
}
return returnMe;
}
private static ArrayList<Integer> getDigitsArray(int number) {
int temp = number;
ArrayList<Integer> array = new ArrayList<Integer>();
do{
array.add(temp % 10);
temp /= 10;
} while (temp > 0);
return array;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.