1
$\begingroup$

I have been given an array whose elements lie between [1,70] and the size of array [1,10^5].

I have to find the total number of subsets whose all elements multiply to give a perfect square number.

Since, count of subsets can be very large, I have to give the ans mod (10^9 + 7).

How should go on to solve this problem ?

One hint given to me is to utilise the range of value that every array element hold which is [1,70] and total no. of prime numbers between these [1,70] are 19.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! Can you credit the original source of this problem? $\endgroup$ – D.W. Sep 20 '18 at 20:14
  • $\begingroup$ I also have the impression that the original source might be easier to decode. $\endgroup$ – gnasher729 Sep 20 '18 at 20:54
3
$\begingroup$

Factor each element $x_i$ to produce a vector $v_i$ of the powers of all primes which are at most 70. The product $\prod_{i \in S} x_i$ is a perfect square if every prime appears in an even power, that is, if $\sum_{i \in S} v_i = \mathbf0 \pmod{2}$. This suggests considering $v_i$ as a vector over $\mathbb{Z}_2$ (the integers mod 2). You are now given a matrix, and wish to know how many subsets of rows sum to the zero vector. This is a problem in linear algebra, and the answer depends on the rank of the matrix: if the matrix has $n$ rows, $m$ columns, and rank $r$, then the answer is $2^{n-r}$.

Here is a worked out example for $1,2,4,5,8$. In this case there are two relevant primes: $2,5$. The full matrix (before reducing modulo 2) is $$ \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 2 & 0 \\ 0 & 1 \\ 3 & 0 \end{bmatrix} $$ After reducing modulo 2, the matrix becomes $$ \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ 1 & 0 \end{bmatrix} $$ This matrix has full rank (rank 2), and so the answer is $2^{5-2} = 8$.

Here are the 8 subsets: $$ \emptyset \\ \{1\} \\ \{4\} \\ \{1,4\} \\ \{2,8\} \\ \{1,2,8\} \\ \{2,4,8\} \\ \{1,2,4,8\} $$

As noted in the comments, you might want to disallow the empty set (which multiplies to 1). In this case, the formula becomes $2^{n-r}-1$.

$\endgroup$
  • $\begingroup$ I understood the part before matrix, but failed to know what you are trying to convey through the matrix part. Do the indices of the row indicate the prime numbers between [1,70] and column indices indicate the number in the given array and each entry in a given cell is the power of row index to produce that number mod 2. $\endgroup$ – Jos Sep 20 '18 at 8:18
  • $\begingroup$ Each row represents an input number. The columns correspond to potential prime factors. The entries correspond to the number of copies of the prime in the prime factorization of the number, reduced modulo 2. $\endgroup$ – Yuval Filmus Sep 20 '18 at 8:22
  • $\begingroup$ Will the above algorithm work for the input array containing 1 . ie- for the input array [1,2,4,5,8]. $\endgroup$ – Jos Sep 20 '18 at 8:25
  • $\begingroup$ Sure, no problem. The corresponding vector is the zero vector. $\endgroup$ – Yuval Filmus Sep 20 '18 at 8:26
  • 1
    $\begingroup$ I’m afraid the point of this otherwise pointless problem is to help you come to grips with linear algebra. As an additional bonus, it will help you calibrate your sense of memory usage. $\endgroup$ – Yuval Filmus Sep 20 '18 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.