Find Two Elements in an Array That Sum to K

How can I find two elements in an array that sum to k

If the numbers stored in the input array are only positive then I'd create another array K of k+1 ArrayList elements. Where k is the number you need them to add up to.
Only two numbers less than k can add up to k (assuming we deal with positive ints} or in special case {0,k}.
Then I would iterate through all elements of input array and for each int m that is less or equal to k I'd take its index and add that index to the array of ArrayList K at index m.
Then I would iterate through first half of the array K and for each index i that has some ints stored in it I would find complementary index [k-i] and see if there are any values in it. If there are then those are your pairs.
And btw this is O(n).

public static void findElemtsThatSumTo( int data[], int k){
    List arrayK[]= new List[k+1];
    for(int i=0; i<arrayK.length; i++)
        arrayK[i]= new ArrayList<Integer>();

    for(int i=0; i<data.length; i++){
        if(data[i]<=k)
            arrayK[data[i]].add(i);
    }

    for(int i=0; i<arrayK.length/2; i++){
        if(!arrayK[i].isEmpty() && !arrayK[k-i].isEmpty())
        {
            for(Object index: arrayK[i])
                for(Object otherIndex: arrayK[k-i])
                    System.out.println("Numbers at indeces ["+index.toString()+", "+otherIndex.toString()+"] add up to "+k+".");
        }
    }

}

Find two elements in an array that sum to k

Make a constant-time lookup table (hash) so you can see if a particular integer is included in your array (O(n)). Then, for each element in the array, see if k-A[i] is included. This takes constant time for each element, so a total of O(n) time. This assumes the elements are distinct; it is not difficult to make it work with repeating elements.

Find if an array can produce a sum n with k number of elements

The base case of your recursive method is incorrect: sum == 0 isn't a sufficient condition you also have to check whether k == 0. If the sum is 0 but you still have to use a few more elements then the result true is incorrect.

The recursive part of the method has some mistakes in it as well. The number of elements summed up k never gets decremented.

Also, you have to track a position in the array. I mean you need to iterate over the array. And while iterating for each element there are only two options: apply it (decrement the k and subtract current value from the sum) or discard it. In both cases, you have to increment the position that you are passing as an argument.

That is how it could be fixed:

    public static boolean groupSum(int[] nums, int k, int pos, int sum) {
        if (sum == 0 && k == 0) {
            return true;
        }
        if (sum < 0) {
            return false;
        }

        boolean result = false;
        for (int i = pos; i < nums.length; i++) {
            boolean takeElement = groupSum(nums, k - 1, pos + 1, sum - nums[i]);
            boolean discardElement = groupSum(nums, k, pos + 1, sum);
            result = takeElement || discardElement;
            if (result) { // a combination that yield the target sum was found
                break;
            }
        }
        return result;
    }

There's another option how to implement this method. But caution: it will be slower and significantly increases memory consumption.

This approach requires creating a copy of the given array with a length decremented by 1 at each recursive method call and pass it as an argument. In this version, an element at position 0 is always used when the method is called, therefore it doesn't require to track the position in the array. The main logic remains the same: a new element can be used either to contribute the sum or can be discarded.

    public static boolean groupSum(int[] nums, int k, int sum) {
        if (sum == 0 && k == 0) {
            return true;
        }
        if (sum < 0 || nums.length == 0) {
            return false;
        }

        boolean takeElement = groupSum(Arrays.copyOfRange(nums, 1, nums.length), k - 1, sum - nums[0]);
        boolean discardElement = groupSum(Arrays.copyOfRange(nums, 1, nums.length), k, sum);

        return takeElement || discardElement;
    }

    public static void main(String[] args) {
        // sum of 1, 2, 3, 4, 5 yields 15 - expected true
        System.out.println(groupSum(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 5, 0, 15));
        // it's impossible with only one element - expected false
        System.out.println(groupSum(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 1, 0, 10));
        // sum of 4, 5, 6 yields 15 - expected true
        System.out.println(groupSum(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 3, 0, 15));
    }

output

true
false
true

Recursion: Determine if there are two elements in an array A that sum to k

Two problems:

1. the j--, will use j first, then --. it should be j - 1 or --j. Same story with i++.

2. The n parameter seems useless. When do use it, index out bounds.

Fixed version with correct result:

public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5, 6};
    System.out.println(sum(a, 6, 7)); // ==> true
}

public static boolean sum(int[] A, int n, int k) //where k is the sum needed and n the size of the array
{
    if (k <= A[0] || k >= A[n - 1] * 2) {
        return false;
    }
    int i = 0;
    int j = n - 1;
    return sum_Recursion(A, n, k, i, j);
}

private static boolean sum_Recursion(int[] A, int n, int k, int i, int j) {
    if (i == j) {
        return false;
    } else if ((A[i] + A[j]) == k) {
        return true;
    } else if ((A[i] + A[j]) > k) {
        return sum_Recursion(A, n, k, i, j - 1);
    }
    return sum_Recursion(A, n, k, i + 1, j);
}

How to find out the sub array where any two elements sum k?

• Add all the numbers greater than k/2 to the subset (keep track of the minimum).

• Go through the array again and add any number greater than k-minimum of subset to the subset. Stop after we added 1.

  If this is part of the requirements, you can look for the biggest one.

This runs in O(n).

The reasoning here is as follows:

• Any 2 elements > k/2 will add up to more than k.
• If one element is <= k/2, the other element will need to be > k/2 to add up to at least k, so there can't be more than one element <= k/2 (since if there were 2, those 2 won't add up to more than k).

An example of this is k = 10, array = [3,4,8,9,10], with the output being [3,8,9,10] or [4,8,9,10]. 8,9,10 will get added in the first step, then we'll add 3 or 4 in the second step.

---

Technical note: "Subset" implies unique elements. We can use a hash table to get expected (but not guaranteed) O(n) complexity. If it's instead a "subsequence" (not unique elements), we can just add them to an array or linked-list for O(n) complexity.

Find if sum of two numbers in an array is equal to k

The Java solution has a check that takes care of two equal elements:

if (map.containsKey(complement) && map.get(complement) != i)

The first part of this condition - map.containsKey(complement) - means that the number complement is present in the Map, while the second part - map.get(complement) != i) - means that the index of complement stored in the map is different from the index i. This means that if complement == nums[i], there are two identical numbers in the input array.

I don't know Python, but it looks like your code fails because

if hash_table[k-x]!= hash_table[x]

always returns false when k-x == x. You need to compare hash_table[k-x] to the current index of the input array.

Based on your first Python loop, I'm assuming the second loop should look like this:

    for i, x in enumerate(nums):
        if k-x in hash_table:
            if hash_table[k-x]!= i:
                return [i, hash_table[k-x]] 

Find Indices of the pair of elements in the Array such that they add up to the Target value

Not sure, but if you are using this code exactly, May it is because of the typo you have after foreach. You are initiating the input as nu, but printing it as num.

.forEach(num -> System.out.println(Arrays.toString(num)));

Perhaps replacing this with what you have will solve the problem.

EDIT

Regarding more clarification over comments, It was realized that was an issue with given values and had nothing to do with Java stream API.

Given a sum of two elements in an int array, how to find their smallest indexes?

Assume a return of [n,m] is an valid output where n<>m and m > 0. Assume a return of [0,0] is an exception output indicates the pair is not found.

There are some mistake in your function:

    public int[] findSumPair(int[] numbers, int k) {

        int[] pairs = new int[2];

        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == k) {
                    // if a pair is found, you could stop looking anymore
                    pairs = new int[] { i, j };

                    // unreachable statement
                    if (numbers[i] + numbers[j] != k) {
                        pairs = new int[] { 0, 0 };
                    }
                }
            }
        }
        return pairs;
    }

Firstly, if you want to find the smallest index, once you found a matched pair, you could break the for-loop. Since you start searching from the left, the first match must be the smallest. No matter now hard the program try, the next result is not the smallest.

Secondly, I think you try to set a false case condition to return [0,0] if no pair is found. However, the condition is contradict to its outer if condition. That is a unreachable statement. You can put that at the very end of the function since when we reach that part, the searching is already completed. I modified the function as:

    public int[] findSumPair(int[] numbers, int k) {

        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == k) {
                    // quit immediately
                    return new int[] { i, j };
                }
            }
        }
        // if we reach here, no pair is found
        return new int[2];
    }

the main()

        int[] result = main.findSumPair(new int[] { 1, 5, 8, 1, 2 }, 13);
        System.out.println(Arrays.toString(result));

        result = main.findSumPair(new int[] { 1, 5, 0, 1, 2, 7, 8, 6 }, 13);
        System.out.println(Arrays.toString(result));

        result = main.findSumPair(new int[] { 1, 2, 2, 2, 2, 1 }, 2);
        System.out.println(Arrays.toString(result));

        result = main.findSumPair(new int[] { 1, 2, 2, 2, 4, 3 }, 7);
        System.out.println(Arrays.toString(result));

        result = main.findSumPair(new int[] { 1, 2, 3, 9, 9, 9, 4 }, 5);
        System.out.println(Arrays.toString(result));

console output

[1, 2]
[5, 7]
[0, 5]
[4, 5]
[0, 6]

---

Related Topics