We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 29
  3. Array Partition
  4. Discussions

Array Partition

  • lufarP
     + 0 comments

    I am getting time out in the last two test cases. I have used DisjointSet and Modular Exponentiation and Euler's Algorithm to solve the problem. My code-

    static int solve(int [] a) 
    {
        DisjointSet<Integer> ds=new DisjointSet<Integer>();
        HashSet<Integer> set=new HashSet<Integer>();
        int count1=0;
        for(int i:a)
             {
                set.add(i);
                ds.makeSet(i);
                if(i==1)
                    count1++;
                
             }
        Iterator <Integer> i=set.iterator();
        while(i.hasNext())
        {
            int x=i.next();
            if(x==1)
                continue;
            else
            {
                Iterator<Integer> j=set.iterator();
                while(j.hasNext())
                {
                    int y=j.next();
                    if(y!=x && gcd(x,y)!=1)
                            ds.union(x,y);
                }
            }       
        }   
        int count=ds.numberOfSets()+(count1!=0?count1-1:0);
        return (int)((power(2,count,1000000007)-2+1000000007)%1000000007);
    }

    Am I missing something?