-
Notifications
You must be signed in to change notification settings - Fork 1
/
ValidacaoDeParenteses.java
49 lines (40 loc) · 1.44 KB
/
ValidacaoDeParenteses.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Desafio
// Dado um inteiro n, retorne o menor número de números quadrados perfeitos cuja soma seja n.
// Um quadrado perfeito é um inteiro que é o quadrado de um inteiro; em outras palavras, é o produto de algum inteiro consigo mesmo.
// Por exemplo, 1, 4, 9 e 16 são quadrados perfeitos, enquanto 3 e 11 não são.
import java.util.*;
public class ValidacaoDeParenteses {
public static void main(String[] args) {
int n = Integer.parseInt(new Scanner(System.in).nextLine());
int res, count, countTotal;
int[] d = new int[n + 1];
for (int i = 1; i < d.length; i++) {
if (i * i <= n) {
d[i] = i * i;
} else {
i = d.length - 1;
}
}
countTotal = 1000;
for (int i = d.length - 1; i> 0 && i <= n; i--) {
if (i >0 && d[i] > 0) {
res = n;
count = 0;
for (int j = i; j > 0; j--) {
while (res > 0) {
if (res >= d[j]) {
res = res - d[j];
count++;
} else {
j--;
}
}
}
if (countTotal > count) {
countTotal = count;
}
}
}
System.out.println(countTotal);
}
}