Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement 
2.1.
Examples
2.1.1.
Input 
2.1.2.
Output
2.1.3.
Explanation
2.1.4.
Input 
2.1.5.
Output
2.1.6.
Explanation
3.
Approach
4.
Algorithm
5.
Implementation in C++
5.1.
Input
5.2.
Output
6.
Implementation in java
6.1.
Input
6.2.
Output
7.
Complexity
7.1.
Time Complexity: 
7.2.
Space Complexity:
8.
Frequently asked questions
8.1.
What is the use of HashMap?
8.2.
What are map and hashmap?
8.3.
Is HashMap a type of array?
8.4.
What is the distinction between a hash map and a hash table?
8.5.
Is HashMap a type of interface?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find four elements that sum to a given value

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.
 

Previous article
Longest Subarray not having more than K Distinct Elements
Next article
Find all permuted rows of a given row in a matrix
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass