trjhtr

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.

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 < 6cdot 10^6, 0 < K < 10^6$. uint_16 is surely insufficient.