Share my 16ms BFS solutiom. is this O(n^2)time or less


  • 1
    U
    int numSquares(int n) 
    {
        deque<int> remain;
        remain.push_back(n);
        
        for (int i = 1, count = 1, nextCount = 0; i < n; ++i, swap(count, nextCount))
        {
            for (; count != 0; --count, remain.pop_front())
            {
                int maxRoot = sqrt(remain.front());
                
                if (maxRoot * maxRoot == remain.front())  { return i; }
                
                for (int endRoot = sqrt(remain.front() / 3); maxRoot >= endRoot; --maxRoot)
                {
                    remain.push_back(remain.front() - maxRoot * maxRoot);
                    ++nextCount;
                }
            }
        }
        return n;
    }
    

    for example:

    if n = 111

    while i = 1

    deque[111]

    and maxRoot == 10

    if (maxRoot^2 == deque.front()) return i

    else

    deque[111 - 1010][111 - 99][111 - 88][111 - 77][111 - 6*6]

    endRoot is 6 (because 5,4,3,2,1 is unnecessary to check, so i cut these)


Log in to reply
 

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