efficient algorithm [Merged]

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • sovixi
    New Member
    • Mar 2007
    • 13

    #1

    efficient algorithm [Merged]

    Hey I'm looking for a solution to the below question. Any recommendations on how to write this algorithm???
    Thanks:


    You are given a sequence s of numbers, in increasing order, for example:

    s = 2, 5, 7, 9, 13, 15.

    You are also given a number n, say n = 16. You have to try to find two numbers x and y from s, such that x+y = n, if such numbers exist. In this example, you could take x = 7 and y = 9.

    However, you must do so as efficiently as possible: you must not perform more additions than the number of elements in s. Describe an algorithm to do this.
  • sovixi
    New Member
    • Mar 2007
    • 13

    #2
    efficient algorithm

    Hey I'm looking for a solution to the below question. Any recommendations on how to write this algorithm???
    Thanks:


    You are given a sequence s of numbers, in increasing order, for example:

    s = 2, 5, 7, 9, 13, 15.

    You are also given a number n, say n = 16. You have to try to find two numbers x and y from s, such that x+y = n, if such numbers exist. In this example, you could take x = 7 and y = 9.

    However, you must do so as efficiently as possible: you must not perform more additions than the number of elements in s. Describe an algorithm to do this.

    Comment

    • weaknessforcats
      Recognized Expert Expert
      • Mar 2007
      • 9214

      #3
      Start at the right.

      Comment

      • JosAH
        Recognized Expert MVP
        • Mar 2007
        • 11453

        #4
        Originally posted by weaknessforcats
        Start at the right.
        Not necessarily so: if n is near the smallest element in s then it's better to
        start at the left.

        kind regards,

        Jos

        Comment

        • sicarie
          Recognized Expert Specialist
          • Nov 2006
          • 4677

          #5
          ::subscribing::

          Comment

          • JosAH
            Recognized Expert MVP
            • Mar 2007
            • 11453

            #6
            Originally posted by sovixi
            Hey I'm looking for a solution to the below question. Any recommendations on how to write this algorithm???
            Thanks:


            You are given a sequence s of numbers, in increasing order, for example:

            s = 2, 5, 7, 9, 13, 15.

            You are also given a number n, say n = 16. You have to try to find two numbers x and y from s, such that x+y = n, if such numbers exist. In this example, you could take x = 7 and y = 9.

            However, you must do so as efficiently as possible: you must not perform more additions than the number of elements in s. Describe an algorithm to do this.
            You asked exactly this same question in the C/C++ forum. Do you want me
            to merge both threads and move them to the 'software development' forum?

            Double posting is considered a nono; don't do that anymore.

            kind regards,

            Jos

            Comment

            • sovixi
              New Member
              • Mar 2007
              • 13

              #7
              any code sugestions how to do it????

              Comment

              • JosAH
                Recognized Expert MVP
                • Mar 2007
                • 11453

                #8
                Originally posted by sovixi
                any code sugestions how to do it????
                Nope, we don't do code here but here's a hint: because set s is sorted in
                ascending order you can find two indexed l and h (h == l+1) such that
                s[l] <= n and s[h] >= n; You can find l and h in O(log(|s|) where |s| is the
                size of set s.

                repeat the following (while applicable)
                x= s[l]+s[h]
                if (x == n) found solution
                else if (x < n) h= h+1
                else l= l-1

                This needs O(|s|) additions at most so voila: problem solved.

                kind regards,

                Jos

                Comment

                • sovixi
                  New Member
                  • Mar 2007
                  • 13

                  #9
                  thanks a lot for your help.

                  Ps I have posted this topic on various forums while looking for an answer. Sorry for that.

                  Comment

                  • JosAH
                    Recognized Expert MVP
                    • Mar 2007
                    • 11453

                    #10
                    Originally posted by sovixi
                    thanks a lot for your help.

                    Ps I have posted this topic on various forums while looking for an answer. Sorry for that.
                    You're welcome of course and don't mention those double posts: I closed your
                    thread in the java forum. I think I'll delete it now.

                    kind regards,

                    Jos

                    Comment

                    Working...