Este exercÃcio me custou algumas muitas horas de resolução. Não tanto pelo enunciado, mas sim pelo desenvolvimento.
O problema pede para que peguemos um int n
que vai delimitar a quantidade de elementos de um array. No exemplo, ele usa n = 5
e devolve um array com 5 elementos, separados por espaço.
5
1 -2 4 -5 1
O intuito é de fazer subarrays a partir desse array, sendo que cada subarray pode ter 1 ou mais posições. Exemplos de arrays que podem ser formados:
Subarrays que podem ser formados começando na posição 0:
[1]
[1, -2]
[1, -2, 4]
[1, -2, 4, -5]
[1, -2, 4, -5, 1]
Subarrays que podem ser formados começando na posição 2:
[4]
[4, -5]
[4, -5, 1]
Subarrays que podem ser formados começando na posição 4:
[1]
Agora que já sabemos como são feitos os subarrays, queremos saber quanto será o resultado da soma deles. Por exemplo:
[1] = 1
[1, -2] = -1
[1, -2, 4] = 3
[1, -2, 4, -5] = -2
[1, -2, 4, -5, 1] = -1
O problema pede para descobrirmos quantos subarrays têm como resultado somas negativas. No caso acima, 3 subarrays têm resultados negativos, mas sabemos que ainda podemos fazer vários outros subarrays e para isso precisamos contabilizar a soma array por array.
=======
Para resolver esse problema, segui o passo a passo:
- Escaneei o
int n
- Fiz um novo array com
n
elementos:int[] array = new int[n]
- Fiz um for que escaneia os valores para todos os
n
elementos
Scanner scanner = new Scanner(new File("input.txt"));
int n = scanner.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = scanner.nextInt();
}
- Declarei a variável
int sum = 0;
- Declarei a variável
int negativeSum = 0;
- Fiz dois
for
, um dentro do outro. O primeirofor (j)
serve para fixar a primeira posição do array, enquanto que o segundofor
(z) vai percorrer todos os elementos seguintes.
for (int j = 0; j < array.length; j++) {
for (int z = j; z < array.length; z++) {
Boolean isNegativeSum = negativeSum(j,z, array);
- Dentro do segundo
for
, será necessário passar um método booleano que faz a soma dos elementos dentro do array e confere se são negativos ou positivos (lembrando que queremos contar apenas os arrays que têm resultados negativos!)
O método passa j
, z
e array
e faz mais uma iteração. Fica assim:
public static Boolean negativeSum(int j, int z, int[] array) {
int sum = 0;
for (int i = j; i <= z; i++) {
sum += array[i];
}
if (sum < 0)
return true;
return false;
Por fim, ao retornar para a main
depois de ter passado pelo método booleano, somamos, através da soma isNegativeSum++
. Código final fica assim:
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = scanner.nextInt();
}
int sum = 0;
int negativeSum = 0;
for (int j = 0; j < array.length; j++) {
for (int z = j; z < array.length; z++) {
Boolean isNegativeSum = negativeSum(j,z, array);
if (isNegativeSum) {
negativeSum++;
}
}
}
System.out.println(negativeSum);
}
public static Boolean negativeSum(int j, int z, int[] array) {
int sum = 0;
for (int i = j; i <= z; i++) {
sum += array[i];
}
if (sum < 0)
return true;
return false;
}
=======
Referências:
How to create a subarray from another array : StackOverFlow
Java array sum average : Baeldung
============
Essa publicação faz parte de uma série de exercÃcios resolvidos em Java no HackerRank. Acesse a série completa:
- HackerRank #6 | Scanner e End-of-file
- HackerRank #7 | Int to String / String to Int
- HackerRank #8 | Date and Time
- HackerRank #9 | Static Initializer Block
- HackerRank #10 | Currency Formatter
- HackerRank #11 | DataTypes
- HackerRank #12 | Strings Introduction
- HackerRank #13 | Substring Comparisons
- HackerRank #14 | Abstract Class
- HackerRank #18 | BigInteger
- HackerRank #19 | Loops II
- HackerRank #20 | String Reverse
- HackerRank #23 | Instanceof keyword
- HackerRank #26 | Generics
- HackerRank #27 | 1D Array
- HackerRank #28 | Anagrams
- HackerRank #33 | Arraylist
- HackerRank #34 | Exception Handling Try / Catch
- HackerRank #36 | Exception Handling
- HackerRank #37 | List
- HackerRank #38 | SubArray
- HackerRank #39 | HashSet
- HackerRank #40 | Java Dequeue
Top comments (2)
Hey can you show the solution in Python?
Sorry, I don't know Python :/