CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: challenged problem C++ implementation - homework help (preparing for an interview).

1. Junior Member Join Date
Jan 2021
Posts
2

## challenged problem C++ implementation - homework help (preparing for an interview).

Hi guys .

I'm struggling to implement in C/C++ a function that gets as two inputs , one input is an integer array, second input is the given sum.

the function returns the pairs of two element that its sum equal to the given sum.

I don't have much experience in C/C++, and I started to implement the function by myself.

I've seen the solution here step by step :
https://www.youtube.com/watch?v=WJP62MCWTM8&t=209s

but I really didn't understand the logic of the explained code in the video, could anyone please explain to me the algorithm / the code that's explained on the video?

how really we find the matched two pairs that its sum equal to the given sum?

For me a pseudo code is also awesome to understand the solution of the problem.

Much appreciated.  Reply With Quote

2. ## Re: challenged problem C++ implementation - homework help (preparing for an interview

Haven't seen the video, but why not code it up as instructed and then step through the code in a debugger?

Imo, there's no better way to learn unknown code than to step through it line by line to see how it works.  Reply With Quote

3. Junior Member Join Date
Jan 2021
Posts
2

## Re: challenged problem C++ implementation - homework help (preparing for an interview Originally Posted by Arjay Haven't seen the video, but why not code it up as instructed and then step through the code in a debugger?

Imo, there's no better way to learn unknown code than to step through it line by line to see how it works.
I understand you, but you're telling me like just copy and paste the code from the video, here I want to learn , copy and
paste codes will not help me now or even on the future , I would do what you suggest without posting this thread.

I posted this thread in order to understand well what's explained on the video and how its explained algorithm match to the problem.

Anyway, Thanks for your reply but it wouldn't help me.  Reply With Quote

4. ## Re: challenged problem C++ implementation - homework help (preparing for an interview

I started to implement the function by myself.
If you post your code then we'll be able to provide guidance re it.

The brute force solution is to start at index 0 (say loop i), then iterate from index i (say loop j) and checking if the sum of the array at positions i and j equal to the required value. Then increment i etc. If the array is sorted, then the loop(s) can be terminated once the sum is greater than the required value.

I'd have a std::vector of std:: pair for the return type.

PS.
If you would like the code from the video explained, then post the actual code (not a link to the video).
Last edited by 2kaud; January 3rd, 2021 at 06:31 AM.  Reply With Quote

5. ## Re: challenged problem C++ implementation - homework help (preparing for an interview

One simple implementation could be:

Code:
```#include <vector>
#include <utility>
#include <iostream>

auto makesum(const std::vector<int>& nos, int sum)
{
std::vector<std::pair<int, int>> fnd;

for (size_t i = 0; i < nos.size(); ++i)
for (size_t j = i; j < nos.size(); ++j)
if (nos[i] + nos[j] == sum)
fnd.emplace_back(nos[i], nos[j]);

return fnd;
}

int main()
{
const std::vector<int> nos {1, 2, 3, 4, 5, 6, 7};

std::cout << "Sum 7\n";
const auto pr7 {makesum(nos, 7)};

for (const auto& [no1, no2] : pr7)
std::cout << no1 << "  " << no2 << '\n';

std::cout << "\nSum 8\n";
const auto pr8 {makesum(nos, 8)};

for (const auto& [no1, no2] : pr8)
std::cout << no1 << "  " << no2 << '\n';
}```
Code:
```Sum 7
1  6
2  5
3  4

Sum 8
1  7
2  6
3  5
4  4```  Reply With Quote

6. ## Re: challenged problem C++ implementation - homework help (preparing for an interview Originally Posted by Ryan Vayer I understand you, but you're telling me like just copy and paste the code from the video, here I want to learn , copy and
paste codes will not help me now or even on the future , I would do what you suggest without posting this thread.

I posted this thread in order to understand well what's explained on the video and how its explained algorithm match to the problem.

Anyway, Thanks for your reply but it wouldn't help me.
I'm not asking you to copy and paste code, I'm asking you to type in the code line by line and think about it while you are typing it.

Then, once the code compiles and runs, step through the code in a debugger and inspect it line by line.  Reply With Quote

7. ## Re: challenged problem C++ implementation - homework help (preparing for an interview Originally Posted by Arjay I'm not asking you to copy and paste code, I'm asking you to type in the code line by line and think about it while you are typing it.

Then, once the code compiles and runs, step through the code in a debugger and inspect it line by line.
Oh wait, you mentioned homework and preparing for an interview.  Reply With Quote

8. Member +   Join Date
Feb 2017
Posts
606

## Re: challenged problem C++ implementation - homework help (preparing for an interview Originally Posted by Ryan Vayer but I really didn't understand the logic of the explained code in the video, could anyone please explain to me the algorithm / the code that's explained on the video?

how really we find the matched two pairs that its sum equal to the given sum?
This problem is quite common and there are several ways to solve it,

https://web.stanford.edu/class/cs9/s...obs/TwoSum.pdf

The video uses the hashtable approach. A hashtable is a data structure where you can store things quickly, for example integers, and then quickly determine whether something, for example a specific integer, is stored or not. In c++ it is called std::unordered_set.

http://www.cplusplus.com/reference/u...unordered_set/

Say there is a sequence of integers,

............a.............b...........

and a+b=sum, so a and b is a valid pair.

1. Start with an empty hashtable.
2. Pick integers x from the sequence one by one from left to right.
3. For each x, check whether sum-x is in the hashtable.
4. If not, insert x into the hashtable and continue.
5. At some point x=a, but you will not find sum-x=b because b has not yet been encountered and therefore is not yet in the hashtable. So you insert x=a into the hashtable and continue.
6. Then after a while x=b is encountered. Check whether sum-x=a is in the hashtable and it is because a has been inserted before.
7. The a and b pair has been found.
Last edited by wolle; January 5th, 2021 at 01:58 AM.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)