22
\$\begingroup\$

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 difference 7 has 2 pairs, 8, 15 and 16, 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?
\$\endgroup\$
  • \$\begingroup\$ {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\$ – Ismael Miguel Aug 27 '15 at 14:47
  • \$\begingroup\$ I actually found the return of all elements, note necessarily unique a lot harder! \$\endgroup\$ – Alexander McFarlane Aug 7 '16 at 1:59
10
\$\begingroup\$

The basic algorithm you use is logical, and well presented. The general style is standard, and I see no issues there. I believe the algorithm can be changed slightly to make the comparison code simpler, but the performance will still be comparable.

I looked for edge cases I would have expected, specifically relating to large differences, but you appear to have covered that well. Unfortunately, your pair-counts for diff == 0 are all off. For example, your third test case:

{new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 0, 18},

should have a count of 6, and not 18. There are only 6 pairs with difference 0. The pair at index 0, and 1, is the same pair as index 1 and 0, so you can't double (or, for some reason triple) count them.

This also applies to cases like: {new int[]{ 1 }, 0, 1},.... you have an input array of just a single element... but you have 1 pair with diff 0? Really???

There is one small performance improvement related to how far you need to iterate in the loop - you have: while (lowIndex < sorted.length && highIndex < sorted.length) { but that can be just while (highIndex < sorted.length) { since lowIndex is always less than or equal to highIndex. This is particularly confusing if your input difference is negative.

For some reason, and I can't explain it, I prefer left and right for those variable names too... lowIndex seems not-quite-right, but I understand it anyway. Just a niggly thing.

Additionally, there are a few places where I would do things in a more Java-8 way. Let's deal with the smaller items first...

Small things

Consider this code:

int[] sorted = Arrays.copyOf(input, input.length);
Arrays.sort(sorted);

I would (now) use the following:

int[] sorted = IntStream.of(input).sorted().toArray();

As for negative difference input values, I would just handle that as an up-front special condition. The count of pairs with a negative difference will be the same as the count with a positive difference and the same magnitude. Just convert negative difference to positive, and handle the Long.MIN_VALUE special case.

Algorithm

I would alter the algorithm a little. I would have a simple scan of the data to count value duplicates, and store that count in a separate array. With that data structure, the search for duplicates later is much easier. Consider this:

    if (input.length <= 1) {
        return 0;
    }

    int[] sorted = IntStream.of(input).sorted().toArray();

    // remove and count duplicate values
    int[] counts = new int[sorted.length];
    int size = 0;
    for (int i = 0; i < sorted.length; i++) {
        if (sorted[i] != sorted[size]) {
            sorted[++size] = sorted[i];
        }
        counts[size]++;
    }
    size++;

The above code ends up with a simpler data set to navigate. Unfortunatley, it makes the case where diff==0 a little more complicated... you need to use factorials for that, and not simple products. (Edit, I extracted that logic completely)....

Still, I put the whole method together as:

import java.util.stream.IntStream;

public class NumberPairsDiff {

    public static int pairsWithDifference(int[] input, long difference) {

        if (input.length <= 1) {
            return 0;
        }

        if (difference == Long.MIN_VALUE) {
            return 0; 
        }

        if (difference < 0) {
            difference = -difference;
        }

        int[] sorted = IntStream.of(input).sorted().toArray();

        // remove and count duplicate values
        int[] counts = new int[sorted.length];
        int size = 0;
        for (int i = 0; i < sorted.length; i++) {
            if (sorted[i] != sorted[size]) {
                sorted[++size] = sorted[i];
            }
            counts[size]++;
        }
        size++;

        if (difference == 0) {
            int pairsFound = 0;
            for (int i = 0; i < size; i++) {
                pairsFound += factorial(counts[i] - 1);
            }
            return pairsFound;
        }

        int left = 0;
        int right = 0;
        int pairsFound = 0;

        while (right < size) {
            long diff = (long)sorted[right] - (long)sorted[left];
            if (diff < difference) {
                right++;
            } else if (diff > difference) {
                left++;
            } else {
                pairsFound += counts[left++] * counts[right++];
            }
        }
        return pairsFound;

    }

    private static int factorial(int n) {
        int f = n;
        while (--n > 1) {
            f *= n;
        }
        return f;
    }

}

The above function fails a bunch of your test cases because it produces the correct results ;-)

\$\endgroup\$
  • \$\begingroup\$ for negative diffs, lowIndex does go higher than highIndex, best way to fix would probably be to do Math.abs(difference). The diff == 0 case also compares elements against themselves (in fact, all diff != 0 does that too but then it will never be true). I let my algorithm determine my requirements, instead of thinking about the requirements. \$\endgroup\$ – Simon Forsberg Aug 28 '15 at 10:18
  • \$\begingroup\$ And then you let your output values from your code be used to set the expected values of your tests? That's the wrong way around..... you should write your tests and then ensure the code gives the right values. \$\endgroup\$ – rolfl Aug 28 '15 at 11:19
  • 1
    \$\begingroup\$ if (difference == Long.MIN_VALUE) return 0;.<-- 0 - Long.MIN_VALUE is a perfectly valid pair? \$\endgroup\$ – Bruno Costa Jun 10 '16 at 9:39
  • 1
    \$\begingroup\$ @BrunoCosta - the inputs are all integers, but the difference is a long. - the maximum difference between two integers is \$2^{32} - 1\$ whihc is way smaller than long's max value. The == MinValue check is just there to prevent a possible issue where the user specifies MIN_VALUE for the long argument, and that cannot be made positive in binary (the negated value of MIN_VALUEis still MIN_VALUE). So, you state: Long.MIN_VALUE is a perfectly valid pair? .... I challenge you to find me two int values that would be a valid pair ;-) \$\endgroup\$ – rolfl Jun 10 '16 at 17:59
  • 1
    \$\begingroup\$ Well, not really, @BrunoCosta There needs to be a check for negative input differerences too. I think what it really needs is a comment (indicating "why"). \$\endgroup\$ – rolfl Jun 10 '16 at 18:32
3
\$\begingroup\$

First of all I am confused about the test cases for difference == 0. If I've only one input, i think the number of pairs is 0 (not 1) because I've no pair. If I've two equal values, i think the number of pairs is 1 (not 3)! And so on....

Apart from that, I tried to use a Map/Hashtable for counting the equal input values (so that there's no need for the findEqual-method.

public static int pairsWithDifference(final int[] input, final long difference) {
    Hashtable<Integer, Integer> equalCounter = new Hashtable<Integer, Integer>();
    for (int singleInput : input) {
        Integer counter = equalCounter.get(singleInput) == null ? 0 : equalCounter.get(singleInput);
        equalCounter.put(singleInput, counter + 1);
    }
    // equalCounter: Hashtable with input as key and amount of equal inputs as value

    // int[] sorted = Arrays.copyOf(input, input.length);
    Integer[] sorted = new Integer[0];
    sorted = equalCounter.keySet().toArray(sorted);
    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 = equalCounter.get(sorted[highIndex]);
            int add;
            if (difference == 0) {
                // 1+2+3+4+5+...+n = 0.5x^2 + 0.5x
                add = (int) (0.5f * highMatching * highMatching + 0.5 * highMatching);
            } else {
                // Find out how many values are equal at `lowIndex`
                int lowMatching = equalCounter.get(sorted[lowIndex]);
                add = lowMatching * highMatching;
            }
            highIndex++;
            lowIndex++;
            pairsFound += add;
        }
    }

    return pairsFound;
}
\$\endgroup\$
  • \$\begingroup\$ but with the findEqual method, there's no need for a HashMap. \$\endgroup\$ – Simon Forsberg Aug 27 '15 at 15:43
  • \$\begingroup\$ The idea of the test cases where difference == 0 was that each number is also equal to itself. Maybe my own requirements there are not the best, but that would be very easy to change (I'd just decrease highMatching by 1 before calculating add) \$\endgroup\$ – Simon Forsberg Aug 27 '15 at 15:45
  • 2
    \$\begingroup\$ also, if you're gonna use a Map, use HashMap. Hashtable is horribly outdated. \$\endgroup\$ – Simon Forsberg Aug 27 '15 at 15:46
  • \$\begingroup\$ There's no special reason why I used Hashtable but the one that I don't need/want null values in my map - so indeed I could have used HashMap instead. \$\endgroup\$ – Niklas P Aug 27 '15 at 15:54
  • \$\begingroup\$ And yes, the decrease of highMatching by 1 would be the only change needed to fit with my interpretation of the requirement. \$\endgroup\$ – Niklas P Aug 27 '15 at 15:55
3
\$\begingroup\$

Floating point police

As a proud member of the Floating Point Police™, I'm issuing you citation for unnecessary use of floating point here:

    int add = (int)(0.5f * highMatching * highMatching + 0.5 * highMatching);

First of all, the equation is wrong. The plus sign should be a minus. But second of all, you don't need floating point since \$n*(n-1)/2\$ is always integral. If you are afraid of integer overflow, you can cast to long:

    long add = (long) highMatching * (highMatching - 1) / 2;
\$\endgroup\$
  • \$\begingroup\$ meta.codereview.stackexchange.com/a/5942/27975 \$\endgroup\$ – h.j.k. Aug 28 '15 at 9:21
  • \$\begingroup\$ The equation isn't wrong for the requirements I put of myself. The fact that those were not very logical requirements is another issue... \$\endgroup\$ – Simon Forsberg Aug 28 '15 at 10:07
  • \$\begingroup\$ @SimonAndréForsberg True, 1+2+...+n is in fact the equation you solved. It's just that you needed to stop at n-1. \$\endgroup\$ – JS1 Aug 28 '15 at 19:26
2
\$\begingroup\$

{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 – Ismael Miguel

Thought I'll provide some advice on this...

One can explore a Builder approach, something like:

private static class TestCaseBuilder {
    private final int[] values;
    private long diff;
    private long expected;

    private TestCaseBuilder(int... values) {
            this.values = values;
    }

    static TestCaseBuilder given(int... values) {
        return new TestCaseBuilder(values);
    }

    TestCaseBuilder andDifference(long diff) {
        this.diff = diff;
        return this;
    }

    TestCaseBuilder expect(long expected) {
        this.expected = expected;
        return this;
    }

    Object[] build() {
        return new Object[]{ values, diff, expected };
    }
}

It becomes (arguably) more readable:

// was
return Arrays.asList(new Object[][]{
        {new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 4, 4},
...

// now
return Arrays.asList(new Object[][]{
        TestCaseBuilder.given(4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42)
                        .andDifference(4).expect(4).build(),
...

Alternatively, drop the Builder in the name and treat this as the testing payload:

public class NumberPairsDiffTest {
    @Parameterized.Parameter
    public TestCase testCase;

    // ...

    @Test
    public void test() {
        String string = String.format("Array %s with diff %d", 
                            Arrays.toString(testCase.values), testCase.diff);
        assertEquals(string, testCase.expected, 
                NumberPairsDiff.pairsWithDifference(testCase.input, testCase.diff));
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You could also have the .expect method return a TestCase directly. \$\endgroup\$ – Simon Forsberg Aug 28 '15 at 10:08
  • \$\begingroup\$ @SimonAndréForsberg yeah, but I wanted to showcase the TestCase-as-a-payload alternative too without touching the code again, so I thought I can leave that conclusion up to the reader (as you did). :) \$\endgroup\$ – h.j.k. Aug 28 '15 at 10:29
1
\$\begingroup\$

My review goes along with most points provided by @rolfl namely about repeating pairs. Although IMO factorial does not suffice for repeating pairs, it's true that in the array [4, 4, 4] you only have the pair (4, 4) but I considered all the possible combinations to be valid pairs thus (4(0), 4(1)), (4(0), 4(2)) and (4(1), 4(2)) are different pairs.

But you can easily have your own approach on how to count those scenarios.

IMO the worst about your code is that you are mixing two different algorithms, the binary search, and the count of pairs. I suggest strongly to separate those.

public static int[] binarySearch(int[] list, int elem)
{
    return binarySearch(list, elem, 0, list.length - 1);
}

public static int[] binarySearch(int[] list, int elem, int left, int right)
{
    int idxFirst = -1;
    int auxRight = right;
    int auxLeft = -1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (list[mid] > elem)
        {
            right = mid - 1;
        }
        else if (list[mid] < elem)
        {
            left = mid + 1;
        }
        else
        {
            if (list[right] > elem)
            {
                auxRight = right + 1;
            }
            right = mid - 1;
            idxFirst = mid;
            auxLeft = auxLeft < 0 ? mid : auxLeft;
        }
    }
    int idxLast = binarySearchLast(list, elem, auxLeft, auxRight);
    return new int[]{idxFirst, idxLast};
}

public static int combinations(int elements, int length)
{
    return factorial(elements, elements - length + 1)/factorial(length, 2);
}

private static int factorial(int n, int stop){
  if(n<=stop){return n;}
  return n * factorial(n-1, stop);
}

private static int binarySearchLast(int[] list, int elem, int left, int right)
{
    int idxLast = -1;
    int mid = left + (right - left) / 2;
    while (left <= right && mid > -1)
    {
        if (list[mid] > elem)
        {
            right = mid - 1;
        }
        else if (list[mid] < elem)
        {
            left = mid + 1;
        }
        else
        {
            left = mid + 1;
            idxLast = mid;
        }
        mid = left + (right - left) / 2;
    }
    return idxLast;
}


public static int pairsWithDifference(int[] input, long difference) {
    if(input.length <= 1){
      return 0;
    }

    int[] sorted = Arrays.copyOf(input, input.length);
    Arrays.sort(sorted);

    int pairsFound = 0;
    for(int i = 0 ; i < sorted.length; ++i){
        int[] interval = binarySearch(sorted, (int)(difference + sorted[i]));
        if(interval[0] > -1){

          boolean sumsTodifference = ((long)sorted[i] - sorted[interval[0]]) == difference || 
              ((long)sorted[interval[0]] - sorted[i]) == difference;

          if(sumsTodifference){
              if(sorted[interval[0]] == sorted[i]){
                //we are on a sequence with repeated numbers
                pairsFound += combinations(interval[1] - interval[0] + 1, 2);
                i = interval[1] + 1;
              }else{
                pairsFound += interval[1] - interval[0] + 1;
              }
          }
        }
    }

    return pairsFound;
}

Those are the tests according to what I would expect:

public static void main (String[] args) throws java.lang.Exception
{
    Object[][]  tests = new Object[][]{
            {new int[]{ 4, 4, 8, 8, 15, 15, 16, 16, 23, 23, 42, 42 }, 0l, 6},
            {new int[]{ 1 }, 0l, 0},
            {new int[]{ 2, 2 }, 0l, 1},
            {new int[]{ 3, 3, 3 }, 0l, 3},
            {new int[]{ 4, 4, 4, 4 }, 0l, 6},
            {new int[]{ 2, 2, 4 }, 0l, 1},
            {new int[]{ 1, 4, 7, 11, 14, 17 }, -3l, 4},
            {new int[]{ 1, 4, 7, 11, 14, 17 }, 5l, 0},
            {new int[]{ Integer.MIN_VALUE, Integer.MAX_VALUE }, (long)(Integer.MAX_VALUE) * 2L + 1L, 1},
    };
    for(Object[] test : tests){
        int pairs = pairsWithDifference((int[])test[0], (long)test[1]);
        System.out.println(pairs + "=" + (int)test[2]);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.