CODEWITHSUNDEEP
javaarrayssum
bonbon
bonbon

Reputation: 21

Find non-repetitive pairs in an array that add up to a given sum

For example, I am provided an array: 1, 3, 9, 6, 5, 8, 3, 4 The problem is that I have to find pairs whose sum is 9 in the array mentioned above. However, the pair must not be repetitive. This means if I already found the first pair [3, 6], then the second pair [6, 3] is not accepted.

The output of this problem should be [1, 8] [3, 6] [5, 4] (no [6, 3] because it is repetitive)

I use Java 8 to solve this problem.

Here are some codes that I tried:

public static void printSumNine(int[] input)
{
    for (int i = 0; i < input.length - 1; i++) {
        for (int j = i + 1; j < input.length; j++) {
            if (9 - input[i] == input[j]) {
                System.out.println("[" + input[i] + ", " + input[j] + "]");
            }
        }
    }
}

Then I put this input in the parameter int input[] = {1, 3, 9, 6, 5, 8, 3, 4};

I expect the output should be:

[1, 8] 
[3, 6]
[5, 4]

but my code produces a different output:

[1, 8]
[3, 6]
[6, 3]
[5, 4]

Upvotes: 2

Views: 1506

Answers (3)

TongChen
TongChen

Reputation: 1430

First,add repeated pairs check for your method,the method like this:

m+n=s,assume m<n,and n-m=x

m+n=m+m+x=s

x=s-2m

since m is different so the x is different so we can use x to identity the pairs,and every pair just need a bit to tag：

public static void printSumNine(int[] input) {
    BitSet checkPool = new BitSet(input.length);
    for (int i = 0; i < input.length - 1; i++) {
        for (int j = i + 1; j < input.length; j++) {
            if (9 - input[i] == input[j]) {
                int checkSum = Math.abs(input[i] - input[j]);
                if (!checkPool.get(checkSum)) {
                    checkPool.flip(checkSum);
                    System.out.println("[" + input[i] + ", " + input[j] + "]");
                }
            }
        }
    }
}

A common method to solve this problem and need costs nlog(n) time and no need other memory：

public static void printSumNine(int[] input, int target) {
        Arrays.sort(input);
        for (int i = 0, j = input.length - 1; i < j; ) {
            int sum = input[i] + input[j];
            if (sum == target) {
                System.out.println("[" + input[i] + ", " + input[j] + "]");
                if (input[i + 1] == input[i]) {
                    i += 2;
                } else {
                    i++;
                }
            } else if (sum > target) {
                if (input[j - 1] == input[j]) {
                    j -= 2;
                } else {
                    j--;
                }
            }
        }
    }

Upvotes: 0

Vimukthi
Vimukthi

Reputation: 880

Try this code. I've used a hashmap to store data. when printing i validate values in hashmap before printing.

public static void main(String[] args) {
    int input[] = {1, 3, 9, 6, 5, 8, 3, 4};
    Map<Integer, Integer> valueMap = new HashMap<>(); 
    for (int i = 0; i < input.length - 1; i++) {
        for (int j = i + 1; j < input.length; j++) {
            if (9 - input[i] == input[j]) {
                if((valueMap.containsKey(input[i])&&valueMap.containsValue(input[j])) || (valueMap.containsKey(input[j])&&valueMap.containsValue(input[i]))) {                          
                    //these are repetitive values
                } else {
                    valueMap.put(input[i], input[j]);
                    System.out.println("[" + input[i] + ", " + input[j] + "]");
                }
            }
        }
    }
}

Upvotes: 0

Tran Ho
Tran Ho

Reputation: 1500

-----**UPDATE for a better solution **------

If you don't mind the order of numbers in pairs, I would suggest you using Set and it needs only O(N) to finish your task better than O(NlogN) in the current solution.

Solution: 

    int N = 9;
    Set<Integer> set = new HashSet<>();
    int[] input = new int[] { 1, 3, 9, 6, 5, 8, 3, 4 };

    for (int i = 0; i < input.length; i++) {
        //condition N = input[i] * 2 is for some cases such as (N = 8, and array contains 2 numbers which have same value 4)
        if (set.contains(N - input[i]) && (!set.contains(input[i]) || (N ==input[i] *2)) {
            System.out.println(input[i] + " - " + (9 - input[i]));
        }
        set.add(input[i]);
    }

The complexity of Hashset.contains is O(1) while you just need to run 1 loop to solve your problem.

I suggest using a Map to remove the duplicate.

Map<Integer, Integer> usedMap

Here is my modified version. Even though its complexity is not good but it is workable. I will edit this post if I can find another approacher with a better complexity.

    Map<Integer, Integer> usedMap = new HashMap<Integer, Integer>();

    int[] input = new int[] { 1, 3, 9, 6, 5, 8, 3, 4 };
    for (int i = 0; i < input.length - 1; i++) {
        if (!usedMap.containsKey(input[i])) {
            for (int j = i + 1; j < input.length; j++) {
                if (!usedMap.containsKey(input[j])) {
                    if (9 - input[i] == input[j]) {
                        System.out.println("[" + input[i] + ", " + input[j] + "]");
                        usedMap.put(input[j], 1);
                    }
                }
            }
            usedMap.put(input[i], 1);
        }

    }

Upvotes: 1

Related Questions