Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1558
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1558
Sum of Two Squares
By Gabriel Dalalio, ITA 
Brazil
Timelimit: 1
Which integer numbers can be represented by a sum of two integer squares?
That is the question that your program must respond!
For example, the number 41 can be represented as (-4)2 + 52 = 41, but 7 cannot be represented in the same way.
Input
The input consists of several lines, each line contains an integer with absolute value less than or equal to 10000.
Output
For each line, print "YES" if the number can be represented by a sum of two integer squares, otherwise print "NO".
| Sample Input | Sample Output |
|
41 7 2 |
YES NO YES |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <math.h>
#define true 1
#define false 0
int main (void)
{
int n;
int x, y;
_Bool ans;
unsigned s;
while (scanf("%d", &n) != EOF)
{
x = 0;
y = sqrt(n);
ans = false;
while (y >= x)
{
s = x * x + y * y;
if (s == n)
{
ans = true;
break;
}
else if (s < n)
++x;
else
--y;
}
printf ("%s\n", ans ? "YES" : "NO");
}
}
Input
41
7
2
7
2
Output
YES
NO
YES
NO
YES
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define MAXN 30000
bool vetor[MAXN];
int main() {
for (int i = 0; i < = 100; i++)
for (int j = 0; j < = 100; j++) {
vetor[i * i + j * j] = true;
}
int n;
while (scanf("%d", &n) != EOF) {
if (n < 0) {
printf("NO\n");
continue;
}
if (vetor[n])
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
Input
41
7
2
7
2
Output
YES
NO
YES
NO
YES
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
static Reader in = new Reader(System.in);
static Writer out = new Writer(System.out);
public static void main(String[] args) throws IOException {
int n;
double root;
boolean f;
while (in.hasNext()) {
n = in.nextInt();
root = Math.sqrt(n);
f = false;
for (int i = 0; i < = root; i++) {
for (int j = 0; j < = root; j++) {
if (i * i + j * j == n) {
f = true;
break;
}
}
if (f == true) {
break;
}
}
out.println(f ? "YES" : "NO");
}
in.close();
out.flush();
out.close();
}
////////// INPUT / OUTPUT //////////
static class Reader implements Closeable {
private final BufferedReader reader;
private StringTokenizer tokenizer;
public Reader(InputStream input) {
reader = new BufferedReader(
new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
private StringTokenizer getTokenizer() throws IOException {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
String line = nextLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer;
}
public boolean hasNext() throws IOException {
return getTokenizer() != null;
}
public String next() throws IOException {
return hasNext() ? tokenizer.nextToken() : null;
}
public String nextLine() throws IOException {
tokenizer = null;
return reader.readLine();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public float nextFloat() throws IOException {
return Float.parseFloat(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public String[] nextStringArray(int size) throws IOException {
String[] array = new String[size];
for (int i = 0; i < size; i++) {
array[i] = next();
}
return array;
}
public int[] nextIntArray(int size) throws IOException {
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = nextInt();
}
return array;
}
public long[] nextLongArray(int size) throws IOException {
long[] array = new long[size];
for (int i = 0; i < size; i++) {
array[i] = nextLong();
}
return array;
}
public double[] nextDoubleArray(int size) throws IOException {
double[] array = new double[size];
for (int i = 0; i < size; i++) {
array[i] = nextDouble();
}
return array;
}
@Override
public void close() throws IOException {
tokenizer = null;
reader.close();
}
}
static class Writer {
private final PrintWriter writer;
public Writer(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void println(Object... objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
public void flush() {
writer.flush();
}
}
}
Input
41
7
2
7
2
Output
YES
NO
YES
NO
YES
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("fs")
const input = readFileSync("/dev/stdin", "utf8").split("\n")
const SquareList = Array.from({ length: 101 }, (_, i) => Math.pow(i, 2))
function isSumOfTwoSquares(num) {
if (num < 0) return false
if (num == 0) return true
const boundary = Math.floor(Math.sqrt(num))
for (let i = 0; i < = boundary; i++) {
for (let j = 0; j < = boundary; j++) {
const sum = SquareList[i] + SquareList[j]
if (sum > num) break
else if (sum == num) return true
}
}
return false
}
function main() {
const responses = []
for (const line of input)
if (line === "") break // EOFile Condition
else responses.push(isSumOfTwoSquares(+line) ? "YES" : "NO")
console.log(responses.join("\n"))
}
main()
Input
41
7
2
7
2
Output
YES
NO
YES
NO
YES
#5 Code Example with Python Programming
Code -
Python Programming
v = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529,
576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764,
1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600,
3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084,
6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216,
9409, 9604, 9801, 10000]
while True:
try: n = int(input())
except: break
p = False
for i in v:
if i >= int(n//2)+1: break
if n-i in v:
p = True
break
print('YES' if p else 'NO')
Input
41
7
2
7
2
Output
YES
NO
YES
NO
YES