Remove a Specific Element of an Array in Java

The challenge

You will be given a certain array of length n, such that n > 4, having positive and negative integers but there will be no zeroes and all the elements will occur once in it.

We may obtain an amount of n sub-arrays of length n - 1, removing one element at a time (from left to right).

For each subarray, let’s calculate the product and sum of its elements with the corresponding absolute value of the quotient, q = SubProduct/SubSum (if it is possible, SubSum cannot be 0). Then we select the array with the lowest value of |q|(absolute value)

e.g.: we have the array, arr = [1, 23, 2, -8, 5]

Sub Arrays            SubSum    SubProduct         |q|
[23, 2, -8, 5]         22         -1840         83.636363
[1, 2, -8, 5]           0           -80          No value
[1, 23, -8, 5]         21          -920         43.809524
[1, 23, 2, 5]          31           230          7.419355  <--- selected array
[1, 23, 2, -8]         18           368         20.444444

Let’s compare the given array with the selected subarray:

[1, 23, 2, -8, 5]
[1, 23, 2,     5]

The difference between them is at the index 3 for the given array, with element -8, so we put both things for a result [3, -8].

That means that to obtain the selected subarray we have to take out the value -8 at index 3. We need a function that receives an array as an argument and outputs the pair [index, arr[index]] that generates the subarray with the lowest value of |q|.

select_subarray([1, 23, 2, -8, 5]) == [3, -8]

Another case:

select_subarray([1, 3, 23, 4, 2, -8, 5, 18]) == [2, 23]

In Javascript the function will be selectSubarray().

We may have some special arrays that may have more than one solution as the one that follows below.

select_subarray([10, 20, -30, 100, 200]) == [[3, 100], [4, 200]]

If there is more than one result the function should output a 2Darray sorted by the index of the element removed from the array.

Thanks to Unnamed for detecting the special cases when we have multiple solutions.

Features of the random tests:

Number of tests = 200
length of the array, l, such that 20 <= l <= 100

The solution in Java code

Option 1:

import static java.util.Arrays.stream;
import static java.util.stream.Collectors.toList;
import static java.util.stream.IntStream.*;

interface Solution {
  static int[][] selectSubarray(int[] arr) {
    var qs = rangeClosed(0, arr.length).mapToDouble(i -> Double.MAX_VALUE).toArray();
    return range(0, arr.length)
        .peek(i -> qs[i] = q(stream(arr).filter(e -> e != arr[i]).toArray()))
        .peek(i -> qs[qs.length - 1] = Math.min(qs[i], qs[qs.length - 1]))
        .boxed().collect(toList()).stream()
        .filter(i -> qs[i] == qs[qs.length - 1])
        .map(i -> new int[]{i, arr[i]})
        .toArray(int[][]::new);
  }

  private static double q(int[] sub) {
    double sum = of(sub).sum();
    double prod = of(sub).mapToDouble(i -> i).reduce(1, (a, b) -> a * b);
    return Math.abs(prod / (sum != 0 ? sum : 1));
  }
}

Option 2:

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;
import static java.math.BigInteger.valueOf;

public class Solution {
  public static int[][] selectSubarray(final int[] arr) {
    final int ss = Arrays.stream(arr).sum();
    final BigInteger pp = Arrays.stream(arr).mapToObj(BigInteger::valueOf).reduce((a, b) -> a.multiply(b)).get();
    ArrayList<int[]> lt = new ArrayList<>();
    BigInteger q = pp.abs();
    BigInteger t;
    for (int i = 0; i < arr.length; i++) {
      if(ss == arr[i]) continue;
      t = pp.divide(valueOf(arr[i])).divide(valueOf(ss - arr[i])).abs();
      
      if (q.compareTo(t) >= 0) {
        if(q.compareTo(t) > 0) lt.clear();
        q = t;
        lt.add(new int[] { i, arr[i] });
      }
    }
    return lt.stream().toArray(a -> new int[a][]);
  }
}

Option 3:

import java.util.stream.*;

public class Solution {
    private static double quotient(final int[] arr, final int exclude) {
        double sum     = IntStream.of(arr).mapToDouble(x -> (double)x)
                                  .sum() - arr[exclude],
               product = IntStream.of(arr).mapToDouble(x -> (double)x)
                                  .reduce(1.0, (a,b) -> a * b) / arr[exclude];
        return sum != 0 ? Math.abs(product / sum) : Double.MAX_VALUE;
    }
    public static int[][] selectSubarray(final int[] arr) {
        double minQ = IntStream.range(0, arr.length)
                               .mapToDouble(i -> quotient(arr, i))
                               .min().getAsDouble();
        return IntStream.range(0, arr.length)
                        .filter(i -> quotient(arr, i) <= minQ)
                        .mapToObj(i -> new int[]{i, arr[i]})
                        .toArray(int[][]::new);
    }
}

Test cases to validate our solution

import org.junit.Test;
import java.util.*;
import java.util.stream.*;

public class SolutionTest {
    @Test
    public void basicTests() {
        Tester.doTest(new int[]{1, 23, 2, -8, 5}, new int[][]{{3, -8}});
        Tester.doTest(new int[]{1, 3, 23, 4, 2, -8, 5, 18}, new int[][]{{2, 23}});
        Tester.doTest(new int[]{10, 20, -30, 100, 200}, new int[][]{{3, 100}, {4, 200}});
    }
    final Random rand = new Random();
    @Test
    public void randomTests() {
        final List<Integer> values = IntStream.concat(IntStream.rangeClosed(-200, -1),
                                                      IntStream.rangeClosed(1, 200))
                                              .boxed().collect(Collectors.toList());
        for (int trial = 1; trial <= 200; trial++) {
            Collections.shuffle(values);
            final int arr[] = values.stream().limit(rand.nextInt(81) + 20)
                                    .mapToInt(x -> x).toArray();
            Tester.doTest(arr, solution(arr));
        }
    }
    public static int[][] solution(final int[] arr) {
        double totalSum = 0.0, totalProduct = 1.0;
        for (int x : arr) {
            totalSum     += x;
            totalProduct *= x;
        }
        double qrr[] = new double[arr.length], qmin = Double.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) 
            if ( totalSum != arr[i] ) {
                qrr[i] = Math.abs(totalProduct / arr[i] / (totalSum - arr[i]));
                qmin = Math.min(qmin, qrr[i]);
            } else
                qrr[i] = Double.MAX_VALUE;
        List<int[]> indices = new ArrayList<>();
        for (int i = 0; i < arr.length; i++)
            if ( qrr[i] <= qmin )
                indices.add(new int[]{i, arr[i]});
        return indices.toArray(int[][]::new);
    }
}
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments