snippetMinor

how to solve simultaneous equation with O(n)

Submitted by: @import:stackexchange-cs·Mar 10, 2026·

Viewed 0 times

withsimultaneoussolvehowequation

Problem

Does someone know how to solve the below?

Assume that the array $A$ is already sorted.
And show an $O(n)$-time algorithm that determines whether or not there exist indices $i,j,k$ such that

$A[i] + 4A[j] = A[i] + 5A[k] = 0$.

I came up with an algorithm that uses two double for-loop for each i, j and i,k. But the complexity will be $O(n^2)$..

Solution

As per a comment of Albert Hendriks, we need to find $i, j, k$ such that $-A[i] = 4A[j] = 5A[k]$.

We can actually do this in a single linear pass. We sweep $i$ from the left, such that $-A[i]$ can only get smaller. We sweep $j, k$ from the right for each possible $i$. But when the left hand side can only get smaller, we don't need to check any $j$ or $k$ again that are bigger than our current $j, k$ since $A$ is sorted, thus our $j, k$ can only ever decrease giving $O(n)$ instead of $O(n^2)$.

In Python:

i = 0
j = k = len(A) - 1

while i = 0 and -A[i] = 0 and -A[i] < 5*A[k]:
       k -= 1

   if -A[i] == 4*A[j] == 5*A[k]:
       return (i, j, k)

   i += 1

return None

Code Snippets

i = 0
j = k = len(A) - 1

while i < len(A):
   while j >= 0 and -A[i] < 4*A[j]:
       j -= 1

   while k >= 0 and -A[i] < 5*A[k]:
       k -= 1

   if -A[i] == 4*A[j] == 5*A[k]:
       return (i, j, k)

   i += 1

return None

Context

StackExchange Computer Science Q#111902, answer score: 2

Revisions (0)

No revisions yet.