DEV Community

Daily Coding Problem #2

Ivan on November 25, 2018

Seeing the first post gained some popularity, here is the second problem For quite some time I found my time procastinating after getting home fro...

Read full post

edh_developer • Nov 26 '18

In python 2.7, no division, O(n) time. The tradeoff is using a bunch of memory, if the list is very long.

values = map(int,raw_input().split(' '))


def getLeftProducts(rawValues):
        leftProducts = []

        if len(rawValues) > 0:
                total = 1
                for val in rawValues:
                        total *= val
                        leftProducts.append(total)

        return leftProducts


def getRightProducts(rawValues):
        rightProducts = []

        if len(rawValues) > 0:
                total = 1
                index = len(rawValues) - 1

                while index >= 0:
                        total *= rawValues[index]
                        rightProducts.insert(0,total)
                        index -= 1

        return rightProducts


def processList(rawValues):
        if len(rawValues) < 2:
                return rawValues

        resultList = []
        leftList = getLeftProducts(rawValues)
        rightList = getRightProducts(rawValues)

        resultList.append(rightList[1])

        index = 1
        while index < (len(rawValues) - 1):
                resultList.append( leftList[index - 1] * rightList[index + 1] )
                index += 1

        resultList.append(leftList[index - 1])

        return resultList


print ' '.join(map(str,processList(values)))

Albin Severinson • Nov 25 '18

Nice find :-)

For the first problem I'd loop over the array twice. The first time to compute the total product and the second time to fill in the output array, dividing out each element of the input array from the total product for the corresponding output element.

I'm guessing that your solution is for the follow-up question though :-). If you have logarithms you could use them to convert multiplication and division to addition and subtraction. This is a common trick when working over finite fields.

Benjamin Braatz • Nov 28 '18

Or with no additional space required:

def prod(input):
    output = []
    right = 1
    for number in reversed(input):
        output.insert(0, right)
        right *= number
    left = 1
    for i, number in enumerate(input):
        output[i] *= left
        left *= number
    return output

Stefano Prosperi • Nov 26 '18 • Edited

O(n) with division, in C#

using System;
using System.Collections.Generic;
using System.Linq;

namespace Daily_Coding_Problem_2
{
    public class Program
    {
        static void Main(string[] args)
        {
            var numbers = GetNumberList();

            var ret = Problem2(numbers);

            foreach (var i in ret)
            {
                Console.WriteLine(i);
            }
        }

        public static IEnumerable<int> GetNumberList()
        {
            return Console.ReadLine() ?
                              .Split(' ')
                              .Select(int.Parse)
                              .ToArray();
        }

        public static IEnumerable<int> Problem2(IEnumerable<int> numbers)
        {
            var enumerable = numbers as int[] ?? numbers.ToArray();

            var product = enumerable.Aggregate(1, (current, n) => current * n);

            return enumerable.Select(n => product / n).ToList();
        }
    }
}

Luiz Guilherme • Nov 25 '18

stackblitz.com/edit/js-xqagwj

const appDiv = document.getElementById('app');

const arr = [1, 2, 3, 4, 5];

const result = arr.map(
  (item) => 
    arr
      .filter(n => n !== item )
      .reduce((acc,current) => acc * current , 1)
);


appDiv.innerHTML = `<h1>RESULT: ${result.toString()}</h1>`;

Hasheen DeBerry • Nov 28 '18

I did something very similar to this. I realised quickly that if any of the numbers in the array are repeated, the totals don’t come out right. I had to explicitly remove the element from the input array and then use the reduce function to calculate the product.
HTH

Gungrave223 • Nov 28 '18 • Edited

const array = [1, 2, 3, 4, 5];

const updated = array.map((ignored, currentIndex) =>
  array.reduce((accum, value, index) => {
    if (currentIndex === index) return accum
    return accum * value;
  }, 1));

Benjamin Braatz • Nov 28 '18

Solution in Python without division, still in O(n²), but inner loop is only executed n²/2 times:

def prod(input):
    output = []
    product = 1
    for number in input:
        for i in range(len(output)):
            output[i] *= number
        output.append(product)
        product *= number
    return output

Markus • Nov 28 '18

Here's my TypeScript version.

This approach works in O(n) by dividing the product of all elements by x[i].

function uberMultiply(x: Array<number>) {
  const product = x.reduce( (a,b) => a * b );
  return x.map(v => product / v);
}

Kasey Speakman • Nov 26 '18 • Edited

Without being aware of possible constraints on the input numbers, a solution with division is most efficient as it conserves both memory (2 array allocations: input and output) and cpu (2 enumerations of the the array, O(2n) ~= O(n)). This was described by @severinson . Here it is in F#.

let calculate arr =
    let product = arr |> Array.reduce (*)
    arr |> Array.map (fun x -> product / x)

To consider a solution without division, understand that we are using division here to reverse a multiplication. An alternative is to choose not to multiply in the first place. But in order to do that, we move to an O( n² ) solution where we shape each element of the output array as we process the input. Then we can choose to selectively skip multiplication.

let calculate arr =
    // initialize the output array to 1s in prep for multiplication
    let output = Array.init (Array.length arr) (fun _ -> 1)
    arr |> Array.iteri (fun i x ->
        output |> Array.iteri (fun j y ->
            if i <> j then output.[j] <- y * x
        )
    )
    output

Note: This function is "pure", despite using mutation internally.

In some branches of mathematics certain operations are not reversible, such as matrix cross product in linear algebra. Perhaps better knowledge of that discipline would yield more efficient algorithms. However, all definitions of this sequence in OEIS use division for calculations.

mdusoemsa • Nov 27 '18

Part 2 solution, slightly better than O(n^2), using a copy to initialize the array, and the inner loop runs 2 fewer times than the outer.

namespace Playground
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = new int[] {1, 2, 3, 4, 5};

            var output = ComputeProducts(input);

            foreach (int i in output)
            {
                Console.Write($"{i}\t");
            }

            Console.ReadLine();
        }

        static int[] ComputeProducts(int[] source)
        {
            var count = source.Length;
            // making a few assumptions for edge cases...
            if (count < 2)
                return source;

            if (count == 2)
                return new[] {source[1], source[0]};

            var result = new int[count];
            // initialize the array, eliminating the need to do a "set to 1" step
            Array.Copy(source,1,result,0,count - 1);
            result[count - 1] = source[0];

            // loop the result
            for (int i = 0; i < count; i++)
            {
                // we skip the current index, and the next one has already been set above
                for (int j = 2; j < count; j++)
                {
                    result[i] *= source[(j + i) % count];
                }
            }

            return result;
        }
    }
}

Ram Kumar R S • Jan 4 '21

def remaining_product(input_array:list)->list:
    new_array = [1 for i in range(len(input_array))]  # output
    for i in range(len(input_array)):
        right_index=[j for j in range(i+1,len(input_array))]
        left_index = [j for j in range(i)]
        all_index= right_index + left_index
        for index in all_index:
            new_array[i] *= input_array[index]
    return (new_array)

Simone Natalini • Nov 27 '18

Don't know if the use of Parallel.ForEach is legit, but here's my take using C# and Linq

static void DoWork(int[] original)
{
   var res = new int[original.Length];
   for (int i = 0; i < original.Count(); i++)
   {
      var notCurrent = original.Where(x => x != original[i]);
      int sum = 1;
      Parallel.ForEach(notCurrent, (notI)=>{ sum = sum*notI;});
      res[i]= sum;
    }
}

chenge • Nov 25 '18 • Edited

def total(arr)
  arr.reduce { |acc, x| acc * x }
end  

arr = [1, 2, 3, 4, 5]
arr.map { |x| total(arr) / x }

Jay • Nov 26 '18

Simple Rust solution:

fn product_array(array: &[i32]) -> Vec<i32> {
    let product = array.iter().fold(1, |acc, n| acc * n);
    array.iter().map(|&n| product / n).collect()
}

For follow-up question:

fn product_array2(array: &[i32]) -> Vec<i32> {
    array
        .iter()
        .map(|&n| {
            array
                .iter()
                .filter(|&i| *i != n)
                .fold(1, |acc, val| acc * val)
        }).collect()
}

Serhii Sakal • Nov 27 '18

JavaScript O(n) but with division:

function Problem02(arr) {
  let mult = arr.slice(1).reduce((a, b) => a * b, 1);
  const res = [mult];

  for (let i = 1; i < arr.length; i++) {
    mult = mult * arr[i - 1] / arr[i];
    res.push(mult); // res[i] = mult;
  }

  console.log(res)
}

Tiago Romero Garcia • Dec 5 '18

Javascript solution, no division, O(n) time.

The idea is basically two steps:

Walk over the list, and for each item, create an object which has the subproduct of itself and all the previous items, and also the item. That takes O(n).
With that list in hand, walk it backwards, for each object multiplying the subproduct of the previous items with the subproduct of the remaining items. That also takes O(n).

I also do a 3rd step to map from that object to the subproducts, but that could be spared if we created a new array during step 1, but still that step would still keep it O(n)

function productOfAllButI(list) {
    const n = list.length;
    const itemsButI = [{product: 1, item: list[0]}];

    for (let i = 1; i < n; i++) {
        const previous = itemsButI[i - 1];
        const item = list[i];
        const product = previous.product * previous.item;
        itemsButI.push({ product, item });
    }

    let remainingSubProduct = 1;
    for (let i = n-1; i >= 0; i--) {        
        const current = itemsButI[i];
        current.product *= remainingSubProduct;
        remainingSubProduct *= current.item;
    }

    return itemsButI.map(({product}) => product);
}

Pavitra Golchha • Nov 25 '18

const pro = a => a.map(i => a.reduce((x, y) => x * y) / i)

pro([1, 2, 3, 4, 5]) // == [120, 60, 40, 30, 24]
pro([3, 2, 1]) // == [2, 3, 6]

Alessandro Scandone • Oct 2 '19

O(n) time, using division, in haskell:

f :: [Int] -> [Int]
f xs = let p = product xs in map (p `quot`) xs

O(n) time, without division, in haskell:

f :: [Int] -> [Int]
f xs = zipWith (*) l r
  where
    l = init $ scanl (*) 1 xs
    r = tail $ scanr (*) 1 xs

websplee • Dec 27 '19

private void ArrayProduct(int arraySize, int [] numArray)
{
int[] prodArray = new int[arraySize];

        for (int i = 0; i < arraySize; i++)
        {
            prodArray[i] = 1;

            for (int k = 0; k < arraySize; k++)
            {
                if(k!=i)
                {
                    prodArray[i] *= numArray[k];
                }
            }

            Console.WriteLine(prodArray[i] + " , ");
        }
    }

Haider Ali • Nov 28 '18

I like the idea, I will be joining it daily. Thanks!

CDLar • Jun 22 '19 • Edited

I used numpy, is that cheating? :⁾

gyazo.com/90a3ac57b8b3339867278e4f...