1. Topic
Given an array of integer n elements, count how many pairs of integers in the array (each integer can only be matched once).
The range of values for n: from 2 to 10 ^ 6.
Sample Input:
1 2 3 | 9 10 20 20 10 10 30 50 10 20 |
Sample Output:
1 2 | 3 |
Describe titles in pictures:
2. Directions.
With connecting the pairs of numbers together which numbers have joined and not considered anymore. Thus we must have an array to store between states.
Browse each element in the array with the remaining elements. If conditions are equal and their state has not been paired, proceed with pairing. Continue with the next number.
3.Code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | static int sockMerchant(int n, int[] ar) { if (n <= 0) return 0; boolean[] status = new boolean[n]; int count = 0; for (int i = 0 ; i < n ; i++) { for (int j = i; j < n ; j++) { if (ar[i] == ar[j] && status[i] == false && status[j] == false && i != j) { status[i] = true; status[j] = true; count++; break; } } } return count; } |