Menu

Quality code matters.

Code challenge: Product of all numbers except the one at i.

In C#, Code ChallengesTags Publish Date139 Views

En este post te voy a explicar como resolví el siguiente challenge:

«Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i»

¿En qué consiste el problema?

Dado un arreglo de números enteros, se debe producir un arreglo del mismo tamaño, que contenga el producto de todos los demás números, excepto del número del índice del número actual.

Por ejemplo: Un arreglo [2,3,4,5]

Va a producir otro arreglo así: [60,40,30,24]

Donde:

  1. arr[0] = 3 * 4 * 5
  2. arr[1]  = 2 * 4 * 5
  3. arr[2] = 2 * 3 * 5
  4. arr[3] = 2 * 3 * 4

Primeros pasos.

Este problema es fácil de resolver por fuerza bruta. La dificultad de este está en encontrar una solución no lineal. El siguiente ejemplo muestra como se uso programación dinámica para almacenar las soluciones temporales. Si te fijas en los números del listado anterior, muchos de ellos se repiten en posición. Puedes soluciones parciales del problema para resolver el ejercicio en su totalidad.

Solución.

using System;
using System.Linq;
using System.Collections.Generic;
class Solution
{
static void Main(string[] args)
{
var array = new[]{0,3,4,5};
var (fromLeftSolutions, fromRightSolutions) = CalculateSolutions(array);
PrintArray(Calculate(array).ToArray());
IEnumerable<int> Calculate(int[] arr) {
for(var i = 0; i <= arr.Length -1 ; i++) {
var value = 1;
if(ShouldCalculateLeft(i)){
value *= CalculateFromLeft(i, fromLeftSolutions);
}
if(ShouldCalculateRight(i, arr)) {
value *= CalculateFromRight(i, fromRightSolutions);
}
yield return value;
}
}
int CalculateFromRight(int index, int[] rightSolutions) => rightSolutions[index + 1];
int CalculateFromLeft(int index, int[] leftSolutions) => leftSolutions[index - 1];
bool ShouldCalculateLeft(int index) => index > 0;
bool ShouldCalculateRight(int index, int[] array) => index < array.Length - 1;
}
private static void PrintArray(int[] array){
foreach(var a in array){
Console.Write($"{a},");
}
Console.WriteLine();
}
private static (int[], int[]) CalculateSolutions(int[] array) {
var maxValue = GetMaxValue(array);
return (CalculateArray(array, maxValue),
(CalculateArray(array.Reverse().ToArray(), maxValue)).Reverse().ToArray());
}
private static int[] CalculateArray(IReadOnlyList<int> array, int maxValue){
var results = new int[array.Count];
var buffer = 1;
for(var i = 0; i < array.Count; i++){
buffer *= array[i];
results[i] = buffer;
}
return results;
}
private static int GetMaxValue(IEnumerable<int> array){
return array.Aggregate(1,(a,b) => a * b);
}
}
view raw Program.cs hosted with ❤ by GitHub

 

Gustavo Sánchez
Últimas entradas de Gustavo Sánchez (ver todo)

Soy especialista en escribir software de calidad. Mediante el uso de marcos de trabajo, técnicas y automatización de procesos he podido reducir los costes operativos de los sistemas de la empresa. Sistemas confiables y adaptables producen clientes felices.

Site Footer