c++ - Find minimum no. of perfect squares that sums to n using BFS algo

Question

We are given an integer n, we have to determine the least no. of perfect squares which sum to n.

Example :

n = 12
and perfect squares up to n are 1, 4, 9, 16, 25... up to n
in this case these will be 1, 4, 9
so output will be 3 as 12 = 4 + 4 + 4

This is code in C++ which implements BFS.

int numSquares(int n) {
    if(n < 0) return -1;
    if(n == 1) return 1;
    vector<int> perfectSqs;
    queue<int> q;
    int level = 0;
    // for(int i=1; i*i<=n; i++) {
    //     perfectSqs.push_back(i*i);
    // }
    // for(int i=0; i<perfectSqs.size(); i++) {
    //     cout<<perfectSqs[i]<<' ';
    // }
    q.push(n);
    while(!q.empty()) {
        int size = q.size();
        for(int i=0; i<size; i++) {
            int curr = q.front();
            q.pop();
            if(curr == 0) return level;
            for(int j=1; j*j<=curr; j++) {
                int next = curr - j*j;
                q.push(next);
            }
        }
        level++;
    }
    return -1;

Everything else runs absolutely fine but time exceeds for input 7168. 7167 also runs.

Can someone let me know where I am wrong?

Answer 1

Concerning efficiciency, you get the same number curr at different times. You must detect it to reduce the time. And try to detect immediately the case next == 0.

Result and benchmark (for n = 7168):

number of squares = 4
932 micro-s
number of squares = 4
OP version: 1258354 micro-s

#include <iostream>
#include <vector>
#include <queue>
#include <chrono>

int numSquares_op(int n) {
    if (n < 0) return -1;
    if (n == 1) return 1;
    //vector<int> perfectSqs;
    std::queue<int> q;
    int level = 0;
    q.push(n);
    while(!q.empty()) {
        int size = q.size();
        for(int i = 0; i < size; i++) {
            int curr = q.front();
            q.pop();
            if(curr == 0) return level;
            for(int j=1; j*j <= curr; j++) {
                int next = curr - j*j;
                q.push(next);
            }
        }
        level++;
    }
    return -1;
    
}

//  New version:

int numSquares(int n) {
    if (n < 0) return -1;
    if (n == 1) return 1;
    std::vector<int> visited (n+1, 0);
    std::queue<int> q;
    int level = 1;
    q.push(n);
    while(!q.empty()) {
        int size = q.size();
        for(int i=0; i<size; i++) {
            int curr = q.front();
            q.pop();
            //if(curr == 0) return level;
            for(int j=1; j*j <= curr; j++) {
                int next = curr - j*j;
                if (next == 0) return level;
                if (visited[next] == 0) q.push(next);
                visited[next] = 1;
            }
        }
        level++;
    }
    return -1;
}

int main() {
    int n;
    std::cin >> n;
    auto t1 = std::chrono::high_resolution_clock::now();
    int nS = numSquares (n);
    std::cout << "number of squares = " << nS << std::endl;
    auto t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();   
    std::cout << duration << " micro-s" << std::endl;
    
//  OP version
    
    t1 = std::chrono::high_resolution_clock::now();
    nS = numSquares_op (n);
    t2 = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
    std::cout << "number of squares = " << nS << std::endl;
    std::cout << "OP version: " << duration << " micro-s" << std::endl;

    return 0;
}