1

I have a list, A, of integers of such that:

  1. len(A) ≥ 2
  2. The first and last elements of A have different signs
  3. All the elements of A are non-zero

I need to write a function that detects the first sign change beside the first and last elements and where O(log n). Is it possible?

def myFunction(A,begin):
    if(begin >= len(A)):
        return [A[0],A[len(A)-1]]
    if(A[begin]>0):
        if(A[begin+1]>0):
            return myFunction(A,begin+1)
        else:
            return [A[begin],A[begin+1]]
    else:
        if (A[begin + 1] < 0):
            return myFunction(A, begin + 1)
        else:
            return [A[begin], A[begin + 1]]
Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Raja
  • 23
  • 1
  • 3
  • Two questions. What code have you tried? Is this a homework problem? – jjramsey May 07 '20 at 19:08
  • 1
    Is the list sorted? – chepner May 07 '20 at 19:09
  • @chepner does it matter? – Feodoran May 07 '20 at 19:11
  • 1
    To determine if this can be done in O(log n), I believe it does. – chepner May 07 '20 at 19:12
  • Oh yeah, right. – Feodoran May 07 '20 at 19:13
  • def myFunction(A,begin): if(begin >= len(A)): return [A[0],A[len(A)-1]] if(A[begin]>0): if(A[begin+1]>0): return myFunction(A,begin+1) else: return [A[begin],A[begin+1]] else: if (A[begin + 1] < 0): return myFunction(A, begin + 1) else: return [A[begin], A[begin + 1]] – Raja May 07 '20 at 19:14
  • i tried this and no the list isnt sorted – Raja May 07 '20 at 19:14
  • @Raja please include the code with propper formatting (intendation) by editing your question. – Feodoran May 07 '20 at 19:16
  • 1
    Please see the guidelines on posting to stack overflow. You should put your formatted code in your original question. Also, if the list isn't sorted, is there at least only 1 sign change in the list? or are there multiple? For example, ```[ -2, -1, 1, 2]`` has one sign change and ```[-2, 1, -3, 2, -4, 5]``` has 5. – sin tribu May 07 '20 at 19:22
  • yes there are multiple i need to find the first one – Raja May 07 '20 at 19:25

3 Answers3

2

This solution is O(log N), because it compares the first element with the middle element, and then continues with only the first or second half of the list. However, this does only work if there is only a single sign change.

def find_sign_change(A):
    if len(A) == 2:
        return 1
    i = len(A) // 2
    if A[0] * A[i] < 0:
        # different sign
        return find_sign_change(A[:i+1])
    else:
        # same sign
        return find_sign_change(A[i:]) + i


print(find_sign_change([3, 4, 6,-6,-5,-3,-5]))
>>> 3
print(find_sign_change([3,-4, 6, 6, 5, 3,-5]))
>>> 6
Feodoran
  • 1,752
  • 1
  • 14
  • 31
0

I thought about something like this for O(log N) (Not sure if it's exactly O(log N) - but it definitely always works ;) )

def func(arr):
    if(len(arr)==2):
        return arr 
    elif(len(arr)==3):
        return arr[:2] if arr[0]*arr[1]<0 else arr[1:]
    else:
        i=0
        l=len(arr)
        while(arr[l//2+i]*arr[0]>0):
            i+=1
        if(l//2+i==l-1):
            for i in range(1, l//2):
                if(arr[i]*arr[i-1]<0):
                    return arr[i-1:i+1]
            return arr[-2:]
        return func(arr[:len(arr)//2+1+i])
Grzegorz Skibinski
  • 12,624
  • 2
  • 11
  • 34
0
def find_sign_change(A):
    for i,(x,y) in enumerate(zip(A,A[1:])):
        if (x>0) - (y>0): break
    return i


print(find_sign_change([3, 4, 6,-6,-5,-3,-5]))
>>> 2
print(find_sign_change([3,-4, 6, 6, 5, 3,-5]))
>>> 0

Or with multiplication (x>0) - (y>0) can be replaced by x*y>0.

I don't think O(log N) is possible.

Friedrich -- Слава Україні
  • 2,901
  • 1
  • 21
  • 40