## Salesforce Interview Question

SDE-2s**Country:**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.