Problem statement:
Write a function which returns the total number of combinations whose difference is
k
.For example,
4 8 15 16 23 42
and the difference7
has 2 pairs,8, 15
and16, 23
.
I liked the Finding number of number pairs with given difference question so much (despite its brokenness) that not only did I review it, but I also decided to write up my own implementation of it (following the approach I described in my review). I was intrigued by this comment:
You need the handle the case of elements being equal too, though. That means an array with 2x duplicates such as
4 4 8 8 15 15 16 16 23 23 42 42
should return 4x the number of combinations as without duplicates. - JS1
When a pair is found, I count how many numbers are matching at lowIndex
and highIndex
respectively, and then calculating how many pairs there are.
NumberPairsDiff.java
public class NumberPairsDiff {
public static int pairsWithDifference(int[] input, long difference) {
int[] sorted = Arrays.copyOf(input, input.length);
Arrays.sort(sorted);
int pairsFound = 0;
int lowIndex = 0;
int highIndex = 0;
while (lowIndex < sorted.length && highIndex < sorted.length) {
long current = (long) sorted[highIndex] - sorted[lowIndex];
if (current < difference) {
highIndex++;
} else if (current > difference) {
lowIndex++;
} else {
// Find out how many values are equal at `highIndex`
int highMatching = findEqual(sorted, highIndex);
highIndex += highMatching;
if (difference == 0) {
// 1+2+3+4+5+...+n = 0.5x^2 + 0.5x
int add = (int)(0.5f * highMatching * highMatching + 0.5 * highMatching);
pairsFound += add;
lowIndex += highMatching;
} else {
// Find out how many values are equal at `lowIndex`
int lowMatching = findEqual(sorted, lowIndex);
lowIndex += lowMatching;
pairsFound += lowMatching * highMatching;
}
}
}
return pairsFound;
}
private static int findEqual(int[] sorted, int index) {
int matching = 1;
while (index < sorted.length - 1 && sorted[index] == sorted[index + 1]) {
index++;
matching++;
}
return matching;
}
}
Obligatory parametrized unit test, NumberPairsDiffTest.java:
@RunWith(Parameterized.class)
public class NumberPairsDiffTest {
@Parameterized.Parameters
public static Collection<Object[]> data() {
return Arrays.asList(new Object[][]{
{new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 4, 4},
{new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 7, 8},
{new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 0, 18},
{new int[]{ 1 }, 0, 1},
{new int[]{ 2, 2 }, 0, 3},
{new int[]{ 3, 3, 3 }, 0, 6},
{new int[]{ 4, 4, 4, 4 }, 0, 10},
{new int[]{ 2, 2, 4 }, 0, 4},
{new int[]{ 1, 4, 7, 11, 14, 17 }, -3, 4},
{new int[]{ 1, 4, 7, 11, 14, 17 }, 5, 0},
{new int[]{ Integer.MIN_VALUE, Integer.MAX_VALUE }, (long)(Integer.MAX_VALUE) * 2L + 1L, 1},
});
}
@Parameterized.Parameter(value = 0)
public int[] input;
@Parameterized.Parameter(value = 1)
public long diff;
@Parameterized.Parameter(value = 2)
public int expected;
@Test
public void test() {
String string = String.format("Array %s with diff %d", Arrays.toString(input), diff);
assertEquals(string, expected, NumberPairsDiff.pairsWithDifference(input, diff));
}
}
Primary concerns
- Readable, understandable code?
- Missed edge-cases?
- Better approaches?
{new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 4, 4}
<-- That really confuses me but I don't see a better way for it \$\endgroup\$