Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
Add Comment
Please, Sign In to add comment