1
\$\begingroup\$

I started doing hackerrank problems only recently and here's my attempt to solve this problem.

Basically, you're given two integers N and K, so you need to find the sum of all 1 <= n <= N such that the sum is at most K away from a perfect square.

For example, for N = 65 and K = 0, we calculate the sum of squares of factors for all numbers from 1 to 65, i.e. 1, 5, 10, ... and see which of these sums is a perfect square (or more precisely 0 away from a perfect square). For 65, that happens to be 1 and 42, so the answer would be 43.

#include <cmath>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

// Lookup table
unordered_map<uint_fast16_t, uint_fast16_t> fac_sq_diff;

auto sum_fac_sq(uint_fast16_t n) {
    uint_fast16_t sum = 0;
    // Calculate factors in pairs,
    // eg. 20 => (1, 20), (2, 10), (4, 5)
    auto sqrtn = sqrt(n);
    for (auto i = 1; i <= sqrtn; ++i) {
        if (n % i == 0) {
            sum += (i * i);
            auto j = n / i;
            if (i != j) {
                sum += (j * j);
            }
        }
    }
    return sum;
}


uint_fast32_t solve(uint_fast16_t n, uint_fast16_t k) {
    uint_fast32_t result = 0;
    int_fast32_t diff = 0;
    for (uint_fast16_t j = 1; j <= n; ++j) {
        auto idiff = fac_sq_diff.find(j);
        if (idiff == fac_sq_diff.end()) {
            auto sum = sum_fac_sq(j);
            // Closest perfect square:
            // https://stackoverflow.com/questions/6054909
            auto sqrtsum = static_cast<uint_fast16_t>(sqrt(static_cast<float>(sum)) + .5f);
            diff = sum - (sqrtsum * sqrtsum);
            diff = abs(diff);
            idiff = fac_sq_diff.emplace(j, diff).first;
        }

        if (idiff->second <= k) {
            result += j;
        }
    }
    return result;
}

int main() {
    // Expected input:
    // 11
    // 65 0
    // 269 1
    // 312 2
    // 745 3
    // 1457 4
    uint_fast16_t q = 1;
    cin >> q;

    // Find max N and reserve lookup table mem
    vector<pair<uint_fast16_t, uint_fast16_t>> NK;
    uint_fast16_t max_N = 0;
    for (auto i = 0; i < q; ++i) {
        uint_fast16_t N = 0, K = 0;
        cin >> N >> K;
        NK.emplace_back(N, K);
        max_N = max(N, max_N);
    }
    fac_sq_diff.reserve(max_N);

    for (auto &nk: NK) {
        cout << solve(nk.first, nk.second) << endl;
    }
    return 0;
}

No matter what I try, I am not able to get past the first test (in terms of speed). :(

I also tried the geometric summation formula to calculate the sum of factors squared, but my implementation turned out to be slower than this one.

\$\endgroup\$
5
\$\begingroup\$

As always, before tackling the Project Euler problems, do your math homework. Few hints:

  • Do not brute force. \$\sigma_2(n)\$ is multiplicative. That allows it to be computed in a much more efficient way.

  • Do not throw away your work. \$\sigma_2(n)\$ does not depend on \$k\$. Tabulate it once toward the maximal possible \$N\$, or extend it as \$N\$ grows.

Besides that, the constraints say \$1 < N < 6\cdot 10^6, 0 < K < 10^6\$. uint_16 is surely insufficient.

\$\endgroup\$
  • \$\begingroup\$ +1 especially for reviewing the code and algorithm without revealing a complete solution and leaving the fun of discovery intact. \$\endgroup\$ – Edward Jul 13 '18 at 20:46
  • \$\begingroup\$ Very helpful information, particularly regarding the multiplicative function. I think I'm back on track, thanks to you. \$\endgroup\$ – user3490458 Jul 14 '18 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.