Problem Solving :: Is it Perfect Square? From toph.co

First time reading the problem i thought it is easy problem.  But soon found it is not an easy problem.
Statement Says:Each test case contains an integer N (1 ≤ N ≤ 10^5), denoting how many numbers to compute. And below that an array A (1 ≤ Ai ≤ 100) consisting of N numbers will be given.
In naive approach all the numbers are multiplied then find it is perfect square or not. That will cause a memory overflow.
After trying some time, I found that only perfect square has the property that every prime factor appeared even number time in factorization.
Example:: 16=2*2*2*, 25=5*5, 225=5*5*3*3.
So i factored each Ai and store the counter of the factor in map. Then finally count if a factor is present with odd count. If there was any odd count then answer false. Or else answer is Yes.
Indeed it is a quite nice problem.

Comments

Post a Comment

Popular posts from this blog

Java notes Date:26/11/2019

#Like C++, when a function is static, run time polymorphism doesn't happen in Java. #Final methods cannot be overridden. #In Java, functions are virtual by default.  #Private methods are final and can not be overridden.   #It is compiler error to give more restrictive access to a derived class function which overrides a base class function. #A java array is always an object. #Arrays in Java are always allocated on heap.  
Read more

Problem Solving:: Be Like Hasib from Toph

Tag of this problem is binary search. Binary search problems seems very interesting to me.  Without thinking much about the problem I submitted a simple binary search algorithm. But got wrong answer 5 or 6 times. But after carefully reading the statement I understood I have to make change to my binary search algorithm. Modified Binary Search:: int count=0;     ll mid=-1;     while(l<h)     {         mid=(l+h)/2;         count++;         //cout<<l<<" "<<h<<" "<<mid<<endl;         if(x==mid)         {             h=mid;             continue;         }      ...
Read more

Problem Solving :: Largest Prime from Toph

In this problem, task is to find out the largest prime number in a given range. Statement says Q (1 ≤ Q ≤ 10 ^5 ), the number of queries that will be given. The next Q lines will contain two integers l i (1 ≤ l i ) and r i (r i ≤ 10000). So for solving this, I used a sieve algorithm for storing all the prime numbers is an array from 1 to 10000. Then I apply binary search for each query.
Read more