Advertisement
Guest User

Untitled

a guest
Mar 26th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.87 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.HashMap;
  5. import java.util.Scanner;
  6.  
  7. /**
  8. * Given an array A of size N, finds all combinations of four elements in the array whose
  9. * sum is equal to K.
  10. * @param args
  11. */
  12.  
  13. public class FindAllFourSumNumbers implements Comparable<FindAllFourSumNumbers> {
  14.  
  15. private int first;
  16. private int second;
  17. private int third;
  18. private int fourth;
  19. private int[] m_arr;
  20.  
  21. /**
  22. * A constructor function which stores four arguments in increasing order
  23. * @param args
  24. */
  25. public FindAllFourSumNumbers(int one, int two, int three, int four) {
  26.  
  27. int[] temp = {one, two, three, four};
  28.  
  29. Arrays.sort(temp);
  30.  
  31. this.m_arr = temp;
  32.  
  33. this.first = temp[0];
  34. this.second = temp[1];
  35. this.third = temp[2];
  36. this.fourth = temp[3];
  37.  
  38. }
  39.  
  40. /**
  41. * Getter function to get the array
  42. */
  43. public int[] getArr() {
  44. return this.m_arr;
  45. }
  46.  
  47. /**
  48. * Making 2 objects equal so long as their m_arr contain the same elements
  49. */
  50. @Override
  51. public boolean equals(Object other) {
  52.  
  53. if (other == null) {
  54. return false;
  55. }
  56.  
  57. if (other == this) {
  58. return true;
  59. }
  60.  
  61. if (!(other instanceof FindAllFourSumNumbers)) {
  62. return false;
  63. }
  64.  
  65. FindAllFourSumNumbers otherObj = (FindAllFourSumNumbers) other;
  66.  
  67. if (!Arrays.equals(this.getArr(), otherObj.getArr())) {
  68. return false;
  69. }
  70.  
  71. return true;
  72.  
  73. }
  74.  
  75. /**
  76. * Overriding the hashCode method as well since equality was over-ridden
  77. */
  78. @Override
  79. public int hashCode() {
  80. return Arrays.hashCode(this.m_arr);
  81. }
  82.  
  83. /**
  84. * Compares two objects by looking at the first element of their m_arr
  85. */
  86. @Override
  87. public int compareTo(FindAllFourSumNumbers other) {
  88.  
  89. int[] myArr = this.getArr();
  90. int[] otherArr = other.getArr();
  91.  
  92. for (int i = 0; i < myArr.length; i++) {
  93.  
  94. int current = myArr[i];
  95. int toCompare = otherArr[i];
  96.  
  97. if (current > toCompare) {
  98. return 1;
  99. } else if (current < toCompare) {
  100. return -1;
  101. }
  102.  
  103. }
  104.  
  105. return 0;
  106.  
  107. }
  108.  
  109. /**
  110. * Allows for the printing of the pair
  111. * @param args
  112. */
  113. public String toString() {
  114.  
  115. return this.first + " " + this.second + " " + this.third + " " + this.fourth + " " + "$";
  116.  
  117. }
  118.  
  119. public static void main(String[] args) {
  120.  
  121. Scanner sc = new Scanner(System.in);
  122.  
  123. //number of test cases
  124. int num = sc.nextInt();
  125.  
  126. for (int t = 0; t < num; t++) {
  127.  
  128. int n = sc.nextInt();
  129. int k = sc.nextInt();
  130.  
  131. //prevents the need for rehashing
  132. HashMap<Integer, ArrayList<FindAllFourSumNumbers>> myMap = new HashMap<>(n);
  133.  
  134. int[] storage = new int[n];
  135.  
  136. for (int i = 0; i < n; i++) {
  137.  
  138. storage[i] = sc.nextInt();
  139.  
  140. }
  141.  
  142. //generate all combinations of a + b + c + d and adding it to the hash map
  143. for (int i = 0; i < n; i++) {
  144.  
  145. for (int j = i + 1; j < n; j++) {
  146.  
  147. for (int l = j + 1; l < n; l++) {
  148.  
  149. for (int m = l + 1; m < n; m++) {
  150.  
  151. int a = storage[i];
  152. int b = storage[j];
  153. int c = storage[l];
  154. int d = storage[m];
  155.  
  156. int sum = a + b + c + d;
  157. FindAllFourSumNumbers myPair = new FindAllFourSumNumbers(a, b, c, d);
  158.  
  159. if (myMap.containsKey(sum)) {
  160.  
  161. ArrayList<FindAllFourSumNumbers> current = myMap.get(sum);
  162.  
  163. if (!current.contains(myPair)) {
  164. current.add(myPair);
  165. }
  166.  
  167. } else {
  168.  
  169. ArrayList<FindAllFourSumNumbers> newList = new ArrayList<>(n);
  170. newList.add(myPair);
  171. myMap.put(sum, newList);
  172.  
  173. }
  174. }
  175. }
  176.  
  177. }
  178.  
  179. }
  180.  
  181. ArrayList<FindAllFourSumNumbers> toPrint = myMap.get(k);
  182.  
  183. if (toPrint != null) {
  184.  
  185. //so that everything is in order
  186. Collections.sort(toPrint);
  187.  
  188. for (int i = 0; i < toPrint.size(); i++) {
  189.  
  190. FindAllFourSumNumbers current = toPrint.get(i);
  191. System.out.print(current.toString());
  192.  
  193. }
  194.  
  195. System.out.println(" ");
  196.  
  197. } else {
  198.  
  199. System.out.println(-1);
  200.  
  201. }
  202.  
  203. }
  204.  
  205. sc.close();
  206.  
  207. }
  208.  
  209. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement