Cassidoo’s Interview question of the week | 455

Learning Resources
1

Hello :waving_hand:

This week question is about finding longest subsequence.

Given an array of positive integers, find the length of the longest subsequence where every adjacent pair of elements in the subsequence is coprime (where the greatest common divisor, or GCD, is 1)

longestCoprimeSubsequence([6, 12, 4, 8])
> 1 // none are coprime

longestCoprimeSubsequence([4, 3, 6, 9, 7, 2])
> 4 // [4, 3, 7, 2], where gcd(4,3)=1, gcd(3,7)=1, gcd(7,2)=1

Happy coding!

1 Like
2

It looks like the result in the second example should be 3, because 4 and 2 are not coprime.

Solution 
def longest_coprime_subsequence(numbers)
  (1..numbers.length - 1).reverse_each do |length|
    numbers.combination(length) do |subsequence|
      return subsequence.length if subsequence
        .flat_map { |n| divisors(n) }
        .tally
        .none? { |n, count| n != 1 && count > 1 }
    end
  end
end

# From https://stackoverflow.com/a/72449326
# I also tried with the Prime gem: https://stackoverflow.com/a/56352354
# but with large inputs it is slower than this approach.
def divisors(n)
  (1..Math.sqrt(n)).each_with_object([]) { |i, arr|
    (n % i).zero? && arr << i && n / i != i && arr << n / i
  }
end