Salesforce Interview Question
SDE-2sCountry: United States
Interview Type: Written Test
#include <bits/stdc++.h>
using namespace std;
int main() {
int x;
cin >> x;
vector<bool> dp(x + 1, false);
dp[1] = true;
for (int i = 2; i <= x; i++) {
int a = sqrt(i);
for (int j = a; j > 0; j--) {
if (!dp[i - pow(j, 2)]) {
dp[i] = true;
break;
}
}
}
for (int i = 1; i <= x; i++) {
cout << i << (dp[i] ? " true" : " false") << endl;
}
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int x;
cin >> x;
vector<bool> dp(x + 1, false);
dp[1] = true;
for (int i = 2; i <= x; i++) {
int a = sqrt(i);
for (int j = a; j > 0; j--) {
if (!dp[i - pow(j, 2)]) {
dp[i] = true;
break;
}
}
}
for (int i = 1; i <= x; i++) {
cout << i << (dp[i] ? " true" : " false") << endl;
}
}
Input X
- N Ghs June 26, 2019Player 1 - We need to backtrack to solve this.
X - Sq(Y) = 0;
i.e, X = Sq(Y) where Y is the last number chosen.
Then further backwards.