GANKAR - Editorial

editorial
, , , ,
1

PROBLEM LINK: Ganesh and Kartik

Author: Rituj Aryan
Tester: Rishabh Rathi

DIFFICULTY:

MEDIUM

PREREQUISITES:

Number Theory

PROBLEM:

Given an array of N integers, find maximum length of contiguous subarray such that there are no two numbers (on different positions) in that array, whose product results in a perfect square.

EXPLANATION:

Observe that product of 2 or more perfect squares is always a perfect square. So dividing a perfect square by a perfect square will also result in a perfect square. Here we will divide all our elements by all perfect squares possible.

Each integer in arr can be represented in the following form:

  • arr[i] = k*x, where k is not divisible by any perfect square other than 1, and x = perfect square,

For example let’s take a number 72 which can be represented as 72=2*36 (2 is not divisible by any other perfect square other than 1 and 36 is a perfect square).

Lets try to represent every element in this form. So for any 2 numbers a and b, they can be represented as

  • a = k_1 * x_1
  • b = k_2 * x_2

Here k_1 and k_2 are not divisible by perfect square and x_1 and x_2 are perfect squares. So for a*b to be a perfect square k_1 should be equal to k_2.

We will represent all elements in this form (Let’s say array B). For this, we can factorize each element and take only those prime numbers which are present odd times in that element.

For eg., 360=2*2*2*3*3*5 (2 and 5 are present odd times so number required will be 5*2 = 10)

Then we need to find longest subarray with unique elements. Steps for it is

  1. Initialize a variable j, to store the maximum value of the index such that there are no repeated elements between index i and j
  2. Traverse the array and keep updating j based on the previous occurrence of arr[i] stored in the HashMap.
  3. After updating j, update ans accordingly to store the maximum length of the desired subarray.

SOLUTIONS:

Setter's Solution (CPP) 
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int t=1; cin>>t;

	while(t--) {
		ll n,i,c,j;
		cin>>n;
		ll a[n];
		map<ll,ll> m;

		for(i=0;i<n;i++)
			cin>>a[i];
		
		for(i=0;i<n;i++) {
			c=a[i];
			m.clear();

			while(c%2==0)  {  
				m[2]++;
				c=c/2;
			}  
			
			for(j=3;j*j<=c;j+=2)  {  
				while(c%j==0)  {  
					m[j]++;  
					c=c/j;  
				}  
			}  

			if(c>1)
				m[c]++;
			
			ll p = 1;
			for(auto e:m) {
				if(e.second%2==1)
					p=p*e.first;
			}
			a[i]=p;
		}

		ll ans=0;
		j=0;
		m.clear();
		for(i=0;i<n;i++) { 
			j =max(m[a[i]], j);
			ans = max(ans, i-j+1);
			m[a[i]] = i+1;
		}
		
		cout<<ans<<"\n";
	}
}
Tester's Solution (Python) 
def primefactorization(c):
	m = {}
	while(c%2 == 0):
		m[2] = m.get(2, 0) + 1
		c //= 2

	j = 3
	while(j*j <= c):
		while(c%j == 0):
			m[j] = m.get(j, 0) + 1
			c //= j
		j += 2

	if c>1:
		m[c] = m.get(c, 0) + 1

	return m


def solve(n, a):
	m = {}

	for i in range(n):
		m = primefactorization(a[i])
		p = 1
		for key in m:
			if m[key]%2:
				p *= key
		a[i] = p

	ans = j = 0
	m = {}
	
	for i in range(n):
		j = max(m.get(a[i], 0), j)
		ans = max(ans, i-j+1)
		m[a[i]] = i+1
	
	return ans


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))

Feel free to share your approach. In case of any doubt or anything is unclear, please ask it in the comments section. Any suggestions are welcome :smile: