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[0]);
//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<>());
map.get(arrWeHave[i] + arrWeHave[j]).add(new Pair(i, j));
}
}
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
You can also read about the Longest Consecutive Sequence.
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
Frequently asked questions
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.
Want to learn more about the Data Structure in java? Click here.
Understand concepts related to the hashmap. It will clear the concept.
Recommended Readings:
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 Coding Ninjas Studio now!
Ninja, have a great time learning.
39+ registered 
