[Codewars] The Sum and The Rest of Certain Pairs of Numbers have to be Perfect Squares (more Challenging)

The Sum and The Rest of Certain Pairs of Numbers have to be Perfect Squares (more Challenging)

  • Time : O(limitlog(limit))
  • Space : O(limit)
c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

std::vector<std::pair<unsigned int, unsigned int>> nClosest(const unsigned int n, const unsigned int k) {
unsigned int lim = n * 2;
vector<int> po;
for(unsigned int i = 1; i * i <= lim; i++) po.push_back(i * i);
vector<pair<unsigned int, unsigned int>> res;
for(int i = n - 1; i >= 0 and res.size() < k; i--) {
auto p = lower_bound(begin(po), end(po), i * 2 + 1) - begin(po);
for(int j = p - 1; j >= 0 and res.size() < k and po[j] > i; j--) {
unsigned int x = po[j] - i;
if(x >= i) continue;
unsigned int t = i - x, sq = sqrt(t);
if(sq * sq == t) res.push_back({i,x});
}
}
return res;
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2023/05/01/PS/Codewars/the-sum-and-the-rest-of-certain-pairs-of-numbers-have-to-be-perfect-squares-more-challenging/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.

Related Issues not found

Please contact @SongHayoung to initialize the comment