Thread: A faster algorithm

  1. #16
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Quote Originally Posted by QuantumPete View Post
    I don't think he did (my emphasis):
    Even if he did take back his solution as if he didn't actually write it, we're back to square one. He needs to post his new attempt. He's still telling everyone to give him the answer. If we ignore his first post completely, all we are left with is him asking us how to do it, having no code or even pseudo-code, or anything even close to anything resembling an attempt.

    Hope is the first step on the road to disappointment.

  2. #17
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Now can anyone suggest me something from this point ?

    I'll give you a suggestion, a real one, but I can promise you that it will be the last one I give if you don't start behaving with a little more understanding of our goals.

    Just in case, our goal here is to support programmers in the C family of languages.

    We help. That is largely the extent of what you will get here.

    You need to sort your target arrays.

    We don't do the work for people.

    You can use elementary mathematics to limit the number of results you need to store.

    We rarely guess at the extent of a persons skill.

    You only need to examine what you've actually stored.

    We rarely guess at the real level of effort a person has offered.


  3. #18
    Registered User
    Join Date
    Sep 2006
    First, I don't know THE best algorithm for this.

    Imagine you had a[5], b[5], and c[5] all int's, and you were given this problem to solve, and had NO computer. Array a[] and b[] each have numbers from 0 to 4, and c has even numbers from 2 to 10 - all these in contiguous indices of 0 to 4.

    a: 0 1 2 3 4
    b: 0 1 2 3 4

    C: 2 4 6 8 10

    We want a[] and b[] to be sorted before anything else (c[] doesn't matter). Might not seem obvious with just 5 numbers, but if each of them had 1,000 numbers, you'd see the advantage quickly, yes?

    So Quicksort (my personal favorite), a[] and b[].

    Now say the target value is 6. Do a binary search for 6 in a[], minus the lowest value in b[], and then increment the index if it's found, to find the first value in a[], greater than the target value - b[]'s lowest value. Save that as "AhighIndex". The answer can't be any higher value.

    Repeat the above on b[], and save it to "BhighIndex".

    Work a similar procedure to the above, finding the AlowIndex and BlowIndex.

    Now your search index range is defined for both a[] and b[]. Note that the above is more complicated only to take advantage of the requirement that the answer must be a[] + b[] == c[], and never simply a[] == c[] or b[] == c[].

    And finally, use two for loops, (one nested inside the other), to find all the answers.

    You may find that sorting just one array (a[] or b[], but not both), and using a binary sort in c[], is all that you need. Before you decide for sure, test it with say, a random array of 20,000 int's in both a[] and b[] (and of course c[] also), and time it with the computer.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. "meeting point" - help with faster algorithm
    By cuber in forum Tech Board
    Replies: 1
    Last Post: 11-01-2011, 08:24 PM
  2. Which is faster?
    By Yarin in forum C++ Programming
    Replies: 4
    Last Post: 08-22-2008, 05:20 PM
  3. What is faster....?
    By Unimatrix_001 in forum C++ Programming
    Replies: 12
    Last Post: 06-15-2003, 09:34 AM
  4. which one is faster....
    By *ClownPimp* in forum C++ Programming
    Replies: 8
    Last Post: 11-10-2002, 01:36 AM
  5. Faster Way?
    By SavesTheDay in forum C Programming
    Replies: 5
    Last Post: 01-23-2002, 06:19 PM