Generalization of a simple linear time algorithm

I am trying to write an O (n) linear time algorithm that defines a table A [0..n-1] (filled with ascending natural values), checks if there exists a pair A [i], A [j] that satisfies f (A [i], A [j]) = C (C is a predefined constant).

Suppose that f (a, b) = a + b algorithm will be:

Algo Paires(A[0..N-1], C)
in: Tab A[0..n-1] and C a constant
out : Boolean
Init indice ← 0
For i ← 0..n-1 do 
    if indice ≠ i & A[indice] + A[i] = C 
      return true
    else if i = n-1 & indice ≤ n-2 
      indice++; i ← 0;
End for
return False

But if:

enter image description here

what will be the algorithm? any suggestions?

+3
source share
1 answer

Hint: suppose there is a 2D matrix whose rows and columns are sorted and you are assigned the number x that you need to find ...

+7
source

All Articles