Hello, I have written a code using nested loop ( 2 for loops ) I am wondering ho

Question

Hello,

I have written a code using nested loop ( 2 for loops ) I am wondering how can I make it even more efficient, instead of using (2 for loops), reduce it to 1 for loop.

here is an example:

for (i=0; i<15; i++)
for (j= i+1; j<15-1;j++)
{
sum =N[i]+N[j];
if ( sum == 15)
cout <<".........";
}

Explanation / Answer

Yes you could make it more efficient, O(n) , with an assumption that you can use additional data structures such as hash map. What you are trying to achieve, I believe, is see if there is a pair of numbers summing up to 15. What you could do is to iterate through an array, and for each a[i] you find on the way, you do the following: 1. Check if there is anything at index a[i] 2. if not, place in the value a[i] at index (15 - a[i]) I am not a c++ coder, so I won;t provide a code to do so, but I know there is an easy to use hash map (or hashtable) class in STL. I will, however, explain how this algorithm works: Each non-empty index in hashmap is telling you that a number of value 15 - index showed up. Now, if we endup looking at a number of value index, then we have already SEEN number 15 - index, now followed by index, therefore BANG! 15 found! Consider the following example: a = [2, 4, 13, 11] 1. val = 2 -> map(2) = Empty (no 13 seen so far) -> map(15 - 2 = 13) = SEEN (Leave a mark for coming 13 so that it knows 2 has been seen) 2. val = 4 -> map (4) = EMPTY -> map(11) = SEEN 3. val = 13 -> map(2) = SEEN -> we have a pair! 4. etc.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.