#include <stdio.h> #include <iostream> #include <unordered_set> using namespace
ID: 3867639 • Letter: #
Question
#include <stdio.h>
#include <iostream>
#include <unordered_set>
using namespace std;
void findPairs(int arr[], int size, int sum)
{
int flag = 1;
unordered_set<int> us;
for(int i=0; i<size; i++)
{
int diff = sum-arr[i];
if(us.find(arr[i])==us.end())
us.insert(diff);
else
{
printf("Two numbers in the array with given sum %d is (%d, %d) ", sum, arr[i], diff);
flag = 0;
}
}
if(flag == 1)
printf("No such sum found. ");
}
int main()
{
int arr[] = {10, 20, 38, 17, 7, 11};
int n = 24;
int size = sizeof(arr)/sizeof(arr[0]);
findPairs(arr, size, n);
return 0;
}
Suppose you are given an array A of length n and a number z. Find an algorithm that determines whether there are any two numbers x and y in the array A such that x + y == z. If so, your algorithm should return those numbers: otherwise, it can return NIL. Your algorithm should run in time O(nlg(n)) and use no more than O(n) storage. Write an algorithm that uses a hash table to solve problem 1 in time O(n) and storage O(n). You may assume that you have access to the functions HASH_SEARCH, HASH_INSERT, and HASH_DELETE, all of which run in time O(1).Explanation / Answer
// solution for problem 1 is already priovided.
// problem 2 solution using hashmap
// C code using hashmap to find sum pair in O(n) time
#include <stdio.h>
#include <stdbool.h>
#define MAX 100000
void findPairs(int arr[], int size, int sum)
{
int t;
bool hashMap[MAX] = {0};
for (int i = 0; i < size; i++)
{
t = sum - arr[i];
if (t >= 0 && hashMap[t] == 1)
printf("Pair with given sum %d is (%d, %d) ", sum, arr[i], t);
hashMap[arr[i]] = 1;
}
}
int main()
{
int arr[] = {10, 20, 38, 17, 7, 11};
int n = 24;
int size = sizeof(arr)/sizeof(arr[0]);
findPairs(arr, size, n);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.