javaarraysarray-indexing

Product of array in a new array except the current index value


Given an array of integers, create 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.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Note: Do not use division.

import java.util.Scanner;
public class Productofarray {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int prod = 1, i, j = 0;
        System.out.println("How many values do you want to enter");
        int n = sc.nextInt();
        int a[] = new int[n];
        int a2[] = new int[n];
        System.out.println("Input " + n + " values:");
        for (i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        for (i = 0; i < n; i++) {
            inner:
            while (j < n) {
                if (a[j] == a[i]) {
                    j++;
                    continue inner;
                }
                prod *= a[j];
            }
            a2[i] = prod;
            System.out.println(a2[i]);
        }
    }
}

I have written this code but the problem is that it is keep on running and it never ends can someone help me what I am doing wrong here.


Solution

  • This should get you closer; as pointed out by Maneesh's answer, you're not checking that you're at the current index i.e i == j instead of a[i]==a[j]. you also do not need the label and it is suggested that you avoid them completely.

    for(int i=0; i<n; i++)
    {
      // this loop can be replaced with a stream.reduce - however that seems to require copying a1 in place to remove the element at index i first as reduce doesn't seem to pass the current index.
      for(int j = 0;  j < n; j++) {
        if(j i) continue;
        a2[i] *= a1[j];
      }
      System.out.println(a2[i]);
    }
    

    it took me a second to figure it out but here's a example using the Java 8 Stream APIs:

    for(int i=0; i<n; i++) // for i -> n
    {
      final int currentIndex = i;
      a2[i] = IntStream.range(0, a1.length)
          .filter(index -> index != currentIndex) // ingore the curent index
          .map(index -> a1[index]) // map the remaining indecies to the values
          .reduce((subTotal, current) -> subTotal * current); // reduce to a single int through multiplication.
    }
    System.out.println(a2[i]);
    

    I haven't tested it but it should work (maybe with a tweak or two). The. gist of it is making a new array (IntStream.range) that contains every element of the given array but the one at currentIndex (.filter().map()) and then multiply the elements (reduce(... subTotal * current)). Note that this solution creates a new array for every iteration through the for loop which, with extremely large arrays, is memory-inefficient.