attiw's blog

By attiw, history, 19 months 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. 

Read more »

Tags gcd
 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it