 New update is available. Click here to update.

# Find four elements that sum to a given value

## Introduction

In this article, we will solve a question on the topic of Hashmap. The Java collections framework's HashMap class offers hash table data structure capability. Key/value pairs are used to store the elements. Here, each value on a map is linked to a key, which acts as a distinctive identifier. The HashMap class implements the Map interface.

## Problem Statement

Assume you have an integer array and a number called sum, according to the problem "Find four entries that sum to a given value (Hashmap)". Determine whether the array has four elements that add up to the provided value "sum" according to the issue statement. If true, the function returns "Yes,". Otherwise, it returns "No."

### Examples

#### Input

``````arrWeHave[] = { 2, 7, 3, 2, 9, 5, 9, 3 }
total_Sum = 25``````

#### Output

``Yes ``

#### Explanation

``If you add the elements 2+9+5+9==25``

#### Input

``````arrWeHave[] = {4, 3, 1, 6, 8, 5, 4, 1}
total_sum=30``````

#### Output

``No``

#### Explanation

``Heare we do not have any possible combinations.``

## Approach

The presented challenge asks us to determine whether the array contains four elements that add to the given value. The function should print yes if the answer is yes. Otherwise, display no. Hashing will be used to address this issue. As a result, we can save the key as an element that pairs with the potential sub-array and the value as an index so that we may check it.

## Algorithm

• While i< n - 1, traverses the loop.

• while j=i+1 < n, transverse the loop.

• Check to see if the sum value is present in the hash table after storing the value of arr[i] + arr[j] to value.

• Obtain the key, ascertain the number, and return true if the answer is yes.

• If not, add those values and the key to the hash table as arr[i] + arr[j].

• Deliver false.

## Implementation in C++

``````#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
typedef pair<int, int> Pair;
bool takeNumber(int arrWeHave[], int n, int total_sum)
{
unordered_map<int, vector<Pair>> map;
//loop
for (int i = 0; i < n - 1; i++)
{
// nested loop
for (int j = i + 1; j < n; j++)
{
int val = total_sum - (arrWeHave[i] + arrWeHave[j]);
if (map.find(val) != map.end())
{
for (auto pair : map.find(val)->second)
{
int fst = pair.first;
int snd = pair.second;
/* cheking for the true value as explaind in algorithm */
if ((fst != i && fst != j) && (snd != i && snd != j))
{
return true;
}
}
}
map[arrWeHave[i] + arrWeHave[j]].push_back({i, j});
}
}
return false;
}
//main code
int main()
{
//given array
int arrWeHave[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
//sum
int total_sum = 25;
//calculating size of array
int n = sizeof(arrWeHave) / sizeof(arrWeHave);
//function pass
if(takeNumber(arrWeHave, n, total_sum))
cout << "Yes";
else
cout<<"No";
return 0;
}``````

### Input

``2, 7, 3, 2, 9, 5, 9, 3``

### Output

``yes``

## Implementation in java

``````import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
// created pair class
class Pair
{
public int fst, snd;
Pair(int fst, int snd)
{
this.fst = snd;
this.fst = snd;
}
}

class CodingNinja
{
public static boolean takeNumber(int[] arrWeHave, int n, int total_sum)
{
// initilizing map
Map<Integer, List<Pair>> map = new HashMap<>();
//loop 1
for (int i = 0; i < n - 1; i++)
{
//nested loop
for (int j = i + 1; j < n; j++)
{
int val= (arrWeHave[i] + arrWeHave[j]);
if (map.containsKey(total_sum-val))
{
//nested loop 2
for (Pair pair : map.get(total_sum-val))
{
int fst = pair.snd;
int fst = pair.snd;
// checking for true comdition
if (fst != i && fst != j) && (snd != i && snd != j))
{
return true;
}
}
}
map.putIfAbsent(arrWeHave[i] + arrWeHave[j], new ArrayList<>());
}
}
return false;
}
//main class
public static void main(String[] args)
{
//input array
int arrWeHave[] = {2, 7, 3, 2, 9, 5, 9, 3};
// declare sum
int total_sum = 25;
// function call
if (takeNumber(arrWeHave, arrWeHave.length, total_sum))
{
System.out.println("Yes");
}
else
System.out.println("No");
}
}``````

### Input

``2, 7, 3, 2, 9, 5, 9, 3``

### Output

``Yes``

## Complexity

### Time Complexity:

O(N^2), Where 'N' stands for the length of the array.

Reason: We discuss an optimised solution that, on average, operates in O(N^2). To hold pair sums, a hashmap is intended to be created.

### Space Complexity:

O(N), Where ‘N’ stands for the array's length.

Reason: N^2 pairs might need to be saved on the map in the worst scenario. Therefore, the complexity of space is polynomial.

Check out this problem - Subarray With 0 Sum

### What is the use of HashMap?

The idea of a map is perhaps implemented most frequently using hashmaps. They enable the association of arbitrary items with other arbitrary objects. Combining or merging data based on a shared attribute can be very helpful.

### What are map and hashmap?

While Map is a Java interface used to map key-pair values, HashMap is a non-synchronized Java Collection Framework class with null values and keys.

### Is HashMap a type of array?

Internally, the HashMap employs an Array and uses a hash function to map labels to array indexes. Hashmap can be implemented in at least two ways: Array: A hash function is used to map a key to the array index value.

### What is the distinction between a hash map and a hash table?

One of the primary distinctions between HashMap and Hashtable is that HashMap is non-synchronized while Hashtable is synchronised. This means that Hashtable is thread-safe and can be shared between multiple threads, whereas HashMap cannot be shared between multiple threads without proper synchronisation.

### Is HashMap a type of interface?

HashMap in Java. The Java HashMap class implements the Map interface, which allows us to store key-value pairs with unique keys. If you try to insert the duplicate key, it will replace the corresponding key's element. The key index makes it simple to perform operations such as updating, deleting, etc.

## Conclusion

This article has gone through a problem related to the hashmap. If you identify any errors or want to add more details about the above subject matter, kindly comment.

Understand concepts related to the hashmap. It will clear the concept.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more?

Please go check out our Operating system course.

Attempt our Online Mock Test Series on CodeStudio now!

Ninja, have a great time learning.  