Find Largest d in Array such that a + b + c = d

Difficulty Level Medium
Frequently asked in Accolite Amazon Delhivery Fanatics Fourkites FreeCharge
Array HashViews 1438

Problem Statement

Suppose you have an array of integers. Input values are all distinct elements. The problem “Find largest d in array such that a + b + c = d” asks to find out the largest element ‘d’ in the set such that a + b + c = d, where all elements are different from each other.

Example

arr[] = {1, 4, 6, 8, 11 }
11

Explanation: The three numbers a, b and c are 1, 4 and 6 and their sum is 11.

arr[] = {2,4,6,10,15 }
No such solution exists.

Explanation: As there are no three numbers, that sums up to a number.

Algorithm

1. Declare a Map.
2. While traversing through the array.
    1. Add and insert the sum of two elements in a map with their indexes in a Map.
3. Set the number to the minimum value of an integer, which we have to find out.
4. Search for the third number in a map by checking the difference of two numbers is present in a map.
5. If true then check if their indexes should not be the same.
6. Check for the maximum of d and the maximum of arr[i] and arr[j] and store it to d.
7. Return d.

Explanation

Consider an integer array consisting of distinct integers. Our task is to find out the number in such a way there exist three numbers which sum up to that number. We are going to use Hashing. Hashing provides an efficient solution. Traverse the array and take two array elements at a time and store the sum of those pairs to map with their respective indexes.

We will store the pair because we are searching for d, such that a + b + c = d. Instead of this, we will be searching for a + b = d – c. So at first, when we store the pair and their indices. We will be able to check for element ‘d’ such that d – c exists in the map. This can be done by traversing the array, and then picking up two elements at once. Make the difference of both the elements and search for that difference if exists in the map. If this found to be true, check the current two elements should not be on the same index as the previous pairs on an index.

This is necessary to check if any of the elements should not be repeated on the same index, the repeated number can be considered in a, b, c and d, but their indices, meant to say, the number itself on the same index should not be considered. So we have to check for those indices plagiarism. Now, we need to find out the maximum of arr[i] and arr[j] and check that maximum to d to find out the maximum between them and store it to the d. Because, we have to find out the fourth number d, so we need to find the maximum of array elements, as d is always bigger among a, b, c and d.

Implementation

C++ program to find largest d in array such that a + b + c = d

#include<iostream>
#include<unordered_map>

using namespace std;

int getSumThreeNumber(int arr[], int n)
{
    unordered_map<int, pair<int, int> > MAP;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            MAP[arr[i] + arr[j]] = { i, j };
        }
    }
    int d_number = INT_MIN;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int third = abs(arr[i] - arr[j]);

            if (MAP.find(third) != MAP.end())
            {
                pair<int, int> obj = MAP[third];
                if (obj.first != i && obj.first != j && obj.second != i && obj.second != j)
                    d_number = max(d_number, max(arr[i], arr[j]));
            }
        }
    }
    return d_number;
}
int main()
{
    int arr[] = { 1,4,6,8,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int res = getSumThreeNumber(arr, n);
    if (res == INT_MIN)
        cout << "No such solution exists";
    else
        cout << res;
    return 0;
}

11

Java program to find largest d in array such that a + b + c = d

import java.util.HashMap;

class CheckIndex
{
    int i, j;

    CheckIndex(int i, int j)
    {
        this.i = i;
        this.j = j;
    }
    int checkI()
    {
        return i;
    }

    int checkJ()
    {
        return j;
    }
}

class sumOfThreeElementToD
{

    public static int getSumThreeNumber(int[] arr, int n)
    {
        HashMap<Integer, CheckIndex> map = new HashMap<>();

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                map.put(arr[i] + arr[j], new CheckIndex(i, j));
            }
        }

        int d_number = Integer.MIN_VALUE;

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int third = Math.abs(arr[i] - arr[j]);

                if (map.containsKey(third))
                {
                    CheckIndex ci = map.get(third);
                    if (ci.checkI() != i && ci.checkI() != j && ci.checkJ() != i && ci.checkJ() != j)
                    {
                        d_number = Math.max(d_number, Math.max(arr[i], arr[j]));
                    }
                }
            }
        }
        return d_number;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 6, 8, 11 };
        int n = arr.length;
        int output = getSumThreeNumber(arr, n);
        if (output == Integer.MIN_VALUE)
            System.out.println("No such solution exists");
        else
            System.out.println(output);
    }
}

11

Complexity Analysis to Find Largest d in Array such that a + b + c = d

Time Complexity

O(n2) where “n” is the number of elements in the array. We have achieved this complexity because we have used HashMap which allows insertion searching and other operations in O(1) time.

Space Complexity

O(n2) where “n” is the number of elements in the array. Since the HashMap stores addition of pair of different elements of the input. Because of this, the algorithm has quadratic space complexity.

Reference

Translate »