om komawar - 1 year ago 71
Java Question

# finding two pairs from integer array out of two elements

Two pairs: If there are two pairs of dice with the same number, the player scores the sum of these dice. If not, the player scores 0. For example, 1, 1, 2, 3, 3 placed on "two pairs" gives 8.

examples:
1,1,2,3,3 results 8
1,1,2,3,4 results 0
1,1,2,2,2 results 6

How can find this efficiently?

I've been using following code to find a single pair

``````int max_difference = 0;
int val1 = 0 , val2 = 0;
Arrays.sort(dice);
for (int i = 0; i < dice.length - 1; i++) {
int x = dice[i+1] - dice[i];
if(x <= max_difference) {
max_difference = x;
val1 = dice[i];
val2 = dice[i+1];

}
}
pairScore = val1 + val2;
``````

I'd use a frequency map, i.e. the number is the key and the value is a counter (so a `Map<Integer, Integer>`). However, since it is used for dices you could simplify that using an array with a length equal to the maximum dice value (6 for standard dice). Then check the frequencies for each number and get the number of pairs from it.

Example:

``````int[] diceFrequency = new int[6];

//assuming d is in the range [1,6]
for( int d : dice ) {
//increment the counter for the dice value
diceFrequency[d-1]++;
}

int numberOfPairs = 0;
int pairSum = 0;

for( int i = 0; i < diceFrequency.length; i++ ) {
//due to integer division you get only the number of pairs,
//i.e. if you have 3x 1 you get 1 pair, for 5x 1 you get 2 pairs
int num = diceFrequency[i] / 2;

//total the number of pairs is just increases
numberOfPairs += num;

//the total value of those pairs is the dice value (i+1)
//multiplied by the number of pairs and 2 (since it's a pair)
pairSum += (i + 1 ) * 2 * num;
}

if( numerOfPairs >= 2 ) {
//you have at least 2 pairs, do whatever is appropriate
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download