attiw's blog

By attiw, history, 7 years ago, In English

I was solving a problem and reduced it to the following.

for each i find smallest j such that j > i and gcd(arr[i], arr[j]) == 1. 

for arr = [2, 6, 3, 2, 5]

for i = 0, j = 2
for i = 1, j = 4
for i = 2, j = 3
for i = 3, j = 4
for i = 4, j = No Found

i taught of stacks.. But don't know to to solve it.

Any solution of O(n) or O(nlogn) will be appreciated. Thank you. 
Tags gcd
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
7 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

constraints n, a[i] ?