Would this Greedy algorithm work??
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Would this Greedy algorithm work??

  1. #1
    Join Date
    May 2010
    Posts
    2

    Would this Greedy algorithm work??

    Hey

    Got an exam on Friday for algorithms, it isnt my strong suit to be honest. Anyways one past paper question asks to design a greedy algorithm:

    Have two arrays, Array Left and Array Right.
    Design an algorithm such that left(i)+right(j)=0

    EG: Left= 3 7 -2 2
    Right=5 -3 -8 -8
    Answer=i=1 and j=2

    Brute force results in worst case quadratic complexity and is an inefficent solution.

    My Solution:

    Put the two arrays together, eg: 2 7 -2 2 5 -3 -8 -8
    Sort them, using mergesort or something. eg -8 -8 -3 -2 2 3 5 7

    Then have two pointers L and R.

    L=1 //starts at begining of array
    R=n // Starts at end of array

    IF L+R < 0 //undershot target value 0
    then
    L=L+1
    else IF L+R >0 //overshot target value 0
    then
    R=R-1

    IF L+R=0 // solution found
    then
    return true

    IF L>R //pointers cross so no solution
    then
    return false

    This seems ok to me, what do you think?? Would result in worst case O(n.log n) due to the merge sort.

  2. #2
    Join Date
    May 2010
    Posts
    2

    Re: Would this Greedy algorithm work??

    Anyone? Just a quick Yes or No would help me out.

  3. #3
    Join Date
    May 2009
    Posts
    2,413

    Re: Would this Greedy algorithm work??

    Quote Originally Posted by smithywill View Post
    Anyone? Just a quick Yes or No would help me out.
    I don't think you have a working algorithm.

    Is the problem that you want to know if a number in one array is present with the opposite sign in the other array? That would make their sum zero, right.

    I don't quite see what merging and sorting the arrays will buy you. By doing that you no longer know which original array each number belongs to. A pair of numbers that sums to zero can as well come from the same array.

    I suggest you just enter all numbers of one array into a hash set. Then you walk through the other array and check whether you have a match with opposite sign in the set. It's an O(N) algorithm.
    Last edited by nuzzle; May 28th, 2010 at 01:00 AM.

  4. #4
    Join Date
    Nov 2010
    Posts
    1

    Re: Would this Greedy algorithm work??

    No it wont work.
    Consider

    Left = 3 -3
    Right = 0 0

    Merged and sorted = -3 0 0 3

    L = 1
    R = n

    IF L+R=0 // solution found
    then
    return true

    Though its obvious thats not true.

    You should sort both left and right separately.

    sort(left)
    sort(right)
    R = n;
    L = 1;
    if L + R < 0
    L = L+1;
    if L + R >0
    R = R - 1;
    if L + R = 0
    return true;

    if(L>n or R<0)
    return false.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center