Desafio de java

Programação Java
,
#1

Bom dia.

Esse é meu primeiro tópico. :slight_smile:

Estive procurando desafio na internet para melhorar meu algorítimo, então encontrei sites de desafios, mas um desafio em especial me soou estranho:
"Write a method which updates an array such that every element becomes the product of every other element."
Não entendi, achei que era o inglês que o meu não é grandes coisas, apesar da frase ser simples, então traduzi e mesmo assim fiquei sem entender.

Traduzida: Escreva um método que atualiza uma matriz de modo que cada elemento se torne o produto de qualquer outro elemento.

Alguém já fez esse desafio ou entendeu o que é para ser feito?

Por exemplo tenho um array: [“branco”,“amarelo”, “vermelho”, “azul”] e agora, o que tenho que fazer?

Eu realmente não entendi oque é para ser feito.

Agradeço desde já.

#2

Pelo que eu entendi, seria o seguinte:

Você tem um array na seguinte forma: [1, 2, 3, 4]

Na hora que você chamar o método que o exercício propõe, ele vai fazer o seguinte: cada elemento vai virar o produto de todos os outros. Seguindo o exemplo, o resultado seria o seguinte:

O elemento na posição 0 vira o número 24 (pois a multiplicação de todos os outros elementos, que não são o elemento na posição 0, ou seja, os elementos nas posições 1, 2 e 3 resulta em 24, 2 x 3 x 4)

O elemento na posição 1 vira o número 12 (1 x 3 x 4)

O elemento na posição 2 vira o número 8 (1 x 2 x 4)

O elemento na posição 3 vira o número 6 (1 x 2 x 3)

O resultado da chamada do método utilizando o array [1, 2, 3, 4] seria o array [24, 12, 8, 6].

É um problema bem interessante. A solução ingênua parece ser percorrer todo o array para cada posição do array (O(nˆ2)). Como otimizar isso? Fica o desafio!

Uma dica: olha o passo a passo que eu dei e tenta achar um padrão na execução das multiplicações. O que está mudando entre elas?

Como você deve ter percebido, a ideia é trabalhar com arrays numéricos. O teu exemplo de cores não se aplica.

(Spoiler - Não leia agora se você quer realmente aprender)

Minha primeira solução:

Cria uma variável e guarda nela a multiplicação do array inteiro. Por exemplo:
x = 1 * 2 * 3 * 4

Depois, cada posição do array a[i] vai ser a[i] = x / a[i].

Esse algoritmo é O(n), porém existe um problema: e se o valor guardado em x não couber em um double? Geralmente as questões de algoritmo tem os boundaries (limites) dos valores que vão ser testados, tem que ver se funciona no caso!

#3

ivbarbosa, Muito obrigado, me ajudou muito.

Eu fiz assim:

p public static void main(String[] args) {
int[] numbers = {1,2,3,4};
BigInteger result = BigInteger.ONE;
BigInteger bInteger[] = new BigInteger[numbers.length];

	for(int number : numbers)
		result = result.multiply(BigInteger.valueOf(number));
	
	for(int iterator = 0; iterator < numbers.length; iterator++ )
		bInteger[iterator] = result.divide(BigInteger.valueOf(numbers[iterator]));
	
	Arrays.stream(bInteger).forEach(element -> System.out.println(element));
}

Aparentemente você já resolveu esse desafio antes. Eu não consigo pensar em uma forma melhor de resolver isso. Eu não deixei O(n^2), mas também não consegui deixar O(n), ficou algo mais como O(n*2).

Como o seu ficou, poderia postar?

Muito obrigado novamente.

#4

Então, eu não resolvi o problema antes, só bolei uma solução na hora que estava escrevendo o post e compartilhei contigo como que eu faria. Consegui enxergar o padrão que te falei enquanto escrevia o exemplo (apenas um número muda, nas multiplicações). O teu algoritmo é O(n) na verdade, o 2 pode ser descartado porque quando a input aumenta, aquele 2 não influencia o desempenho do algoritmo de maneira exponencial :slight_smile:

Não consigo enxergar outra solução sem pensar muito, mas caso eu bole algo, venho aqui compartilhar contigo. Eu não implementaria muito diferente do que você fez não, só faria mais dinâmico (com a possibilidade de inputs de tamanhos variados). Se funcionou tá ótimo!

Você fez em algum site de exercícios? Se sim, passou no teste? Geralmente eles tem um limite de tempo de execução e só passa se estiver dentro do limite de complexidade.

PS: Não respondi mais cedo porque criei minha conta aqui ontem, estava bloqueado de postar porque era meu primeiro dia.

#5

Ha, entendi!

Então, os desafios não peguei de sites tipo codility, eu estou vasculhando questões de entrevista exemplo: http://techinterviewsolutions.net/2012/08/amazon-interview-questions-cheatsheet/ , mas esse em especial não lembro qual site peguei, copiei vários desafios de vários sites diferentes. :smiley:

Muito Obrigado lvbarbosa.

Vou marcar sua primeira resposta como solução do problema.

#6

De nada!

Eu gosto bastante de resolver problemas no CodeChef. Recomendo, se quiser dar uma olhada! Tem vários desafios, separados por níveis, contextualizados com historinhas para facilitar o entendimento.

Eles tem também um esquema de avaliar o teu código. Você submete o source file e eles dizem se você passou ou não.

Tem vários outros, como o HackerRank e o Codeforces que seguem a mesma linha do CodeChef. É uma maneira legal de passar o tempo livre :slight_smile: