The smallest subsequence

3

8 votes
Graphs, Algorithms, Breadth-first search, C++
Problem

You are given an array A that contains N integer elements. The value A[i] of every element is such that the number of divisors of A[i] is at most 7.

Find the length of the smallest non-empty subsequence of this array such that the product of elements in the subsequence is a perfect square. If no such subsequence exists, then print -1.

A sequence A is a subsequence of an array B if A can be obtained from B by deleting several (possibly, zero or all) elements.

Input format

  • The first line contains an integer N denoting the number of elements in the array.
  • The second line contains N space-separated integers denoting array A.

Output format

Print an integer, denoting the length of the smallest non-empty subsequence of the array that satisfies the mentioned conditions.

Constraints

1N1051A[i]106

  

Time Limit: 1.5
Memory Limit: 256
Source Limit:
Explanation
  • Choose the subsequence [6,6] , length of the subsequence is and product is 36 which is a perfect square.
Editor Image

?