Code Wars III - Two Sum [ENG-ESP]

Solving the kata [Resolviendo el kata]

This is a fairly simple exercise. First of all we declare an array of length 2, which is where we are going to place the indexes of those 2 numbers that add up the amount we are asked for. Then we are going to iterate over the array. We have 2 nested loops, since we are going to use the one outside as an anchor to add the rest of the elements of the array. Because we must find 2 different numbers in order to get that sum, the inner loop must not start at the same index as the outer one, that's why the iterator variable is always initialized to the successor of the other variable. This way we make sure that we never add the same element twice. Then we have a very simple condition: if the number with the index i added with the one that has the index j results in the target number, then we are going to place the indices of those numbers in the array the function will return.

Este es un ejercicio bastante sencillo. Primero que todo declaramos un array de longitud 2, que es donde vamos a colocar los índices de aquellos 2 números que sumen la cantidad que se nos pide. Luego vamos a recorrer el array. Tenemos 2 bucles anidados, ya que vamos a usar el de afuera como ancla para sumarle el resto de elementos del array. Debido a que para obtener dicha suma debemos encontrar 2 números diferentes, el bucle interior no debe comenzar en el mismo índice que el externo, es por eso que la variable iteradora siempre se inicializa en el sucesor de la otra variable. Así nos aseguramos que nunca sume el mismo elemento 2 veces. Después tenemos una condición bien sencilla: si el número en la casilla i sumado con el número en la casilla j da como resultado el número objetivo, entonces vamos a colocar los índices de esos números en el array que la función luego va a devolver.

If there are different pairs of numbers that result in the correct number, the method will end up returning the last pair and, although the exercise allows us to return any pairs of numbers, in the end we end up executing extra operations. Since the exercise asks for only one pair and assures us that there will always be a pair available, whose sum will be equal to target, the method can be simplified in this way, assuring us that the last return will never be executed. Either way, the 2 ways of doing it are perfectly valid, so you can choose either of them.

Si hay distintos pares de números que dan como resultado el número correcto, el método terminará devolviendo el último par y, aunque el ejercicio nos permite devolver cualesquiera pares de números, al final terminamos ejecutando operaciones extra. Ya que el ejercicio nos pide tan solo un par y nos asegura que siempre habrá un par disponible, cuya suma será igual a target, el método se puede simplificar de esta manera, asegurándonos que el último return jamás se ejecutará. De cualquier manera, las 2 formas de hacerlo son perfectamente válidas, así que se pueden escoger cualquiera de ellas.

Alternatives solutions [Soluciones alternativas]

User JoZzzward chose a solution using the generic class Dictionary<T>. After declaring the dictionary, it goes through the array of numbers and, at each iteration, finds the difference between target and the current element. Using a conditional it asks if the dictionary contains a key equal to the previous difference. If so, it means that it had already found in the array another number that added with the current element results in the number we were looking for, and then the method will return a new array with the indexes of both numbers. In a second conditional it adds a new key-value pair with the current element as key and its index as value, if that key is not yet found in the dictionary. The idea is to see if we find some element that subtracted from target gives us as result some of the keys that are already in the dictionary; in other words: if the sum of the current element with some of the keys of the dictionary gives as result the number that we wanted to find. Finally it returns an empty array, although as we have already seen, due to the particularities of this exercise, this line of code will never be executed.
This solution is more efficient than my 2 proposed solutions. While those used 2 nested loops, which means a complexity of O(n^2), user JoZzzward's solution takes advantage of the efficiency of dictionaries to look up an element by its key and only needs a single loop to operate, so it has a complexity of O(n), a linear complexity.

El usuario JoZzzward escogió una solución usando la clase genérica Dictionary<T>. Luego de declarar el diccionario, recorre el arreglo de números y, en cada iteración, halla la diferencia entre target y el elemento actual. Utilizando un condicional se pregunta si el diccionario contiene una clave igual a la diferencia anterior. De ser así significa que ya había encontrado en el array otro número que sumado con el elemento actual da como resultado el número que buscábamos y, a continuación, el método devolverá un nuevo array con los índices de ambos números. En un segundo condicional añade un nuevo par clave-valor con el elemento actual como clave y su índice como valor, si dicha clave no se encuentra aún en el diccionario. La idea es ver si al seguir iterando encontramos algún elemento que, substraído de target, dé como resultado alguna de las claves que se encuentran en el diccionario, o en otras palabras: si la suma del elemento actual con alguna de las claves del diccionario da como resultado el número que queríamos encontrar. Por último devuelve un array vacío, aunque como ya vimos, debido a las particularidades de este ejercicio, esa línea de código jamás se ejecutará.
Esta solución es más eficiente que mis 2 soluciones propuestas. Mientras aquellas usaban 2 bucles anidados, lo cual significa una complejidad de O(n^2), la solución del usuario JoZzzward se aprovecha de la eficiencia de los diccionarios para buscar un elemento por su clave y sólo necesita de un único bucle para operar, por lo que tiene una complejidad de O(n), una complejidad lineal.

This solution belongs to user Acceptme3. In a first condition, we check if the current element is greater than target. Then we can discard this number, since this means that there is no other number in the array that when added with this one gives such a result, so we can therefore move on to the next iteration. The exercise does not say anything about whether all the elements of the array are positive, but we can assume this thanks to this first conditional. If this condition is false we will compute the difference between target and the current element, using the auxiliary method Difference(). In the inner loop we will compare this result with each of the remaining elements of the array and, if they are equal, we will return an array with the indices of the valid elements. This solution is a little more efficient than mine in some specific cases, when encountering elements larger than target, but in general terms it has the same complexity: O(n^2).

Esta solución pertenece al usuario Acceptme3. En una primera condición, chequeamos si el elemento actual es mayor que target. Así podremos desechar este número, ya que significará que no hay ningún otro número en el array que al sumarlo con este dé dicho resultado y que, por tanto, podremos pasar a la siguiente iteración del bucle. El ejercicio no dice nada acerca de si todos los elementos del array son positivos, pero podemos asumirlo de esta manera gracias a este primer condicional. De ser falsa está condición tomaremos la diferencia entre target y el elemento actual, utilizando el método auxiliar Difference(). En el bucle interior compararemos esta diferencia con cada uno de los elementos restantes del array y, de ser iguales, devolveremos un array con los índices de los elementos válidos. Esta solución es un poco más eficiente que la mía en algunos casos específicos, cuando se encuentra con elementos más grandes que target, pero en términos generales tiene la misma complejidad: O(n^2).

That is all for today. In the next post I will be analyzing another pretty interesting alternatives solutions.

Eso es todo por hoy. En el próximo post estaremos analizando otras soluciones alternativas bastante interesantes.

English translation made with DeeplTranslate
Traducción al inglés hecha con DeeplTranslate