PERFECT SQUARES using Java


  • 0
    class Solution {
        public int numSquares(int n) {
            if(n<2)
                return n;
            
            Queue<Integer> nums = new LinkedList<Integer>();
            Set<Integer> tempQ = new HashSet<Integer>();
            nums.add(n);
            int count=1, finalCount = 0;
            
            while(!nums.isEmpty())
            {
                int num = nums.remove();
                for(int i = 1; (i*i) <=num; i++)
                {
                    if(num - (i*i) < 0)
                        break;
                    
                    if(num >= (i*i))
                        if(num - (i*i) == 0)
                        {
                            finalCount = count;
                            break;
                        }
                        tempQ.add(num - (i*i));
                }
                
                if(nums.isEmpty())
                {
                    count++;
                    Iterator<Integer> it = tempQ.iterator();
                    while(it.hasNext())  {
                        nums.add(it.next());
                    }
                }
                if(finalCount != 0)
                    break;
            }
            return finalCount;
            
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.