Find the number that can be divided from a array of numbers-CodePudding

Find the smallest number M, which is divided by exactly n-1 numbers from the input array. If there is no such M then return -1.

Example:

array = [2,3,5]

Answer :

Explanation :

6 can be divided by 2 and 3

Example:

array = [2,3,6]

Answer:

-1

Explanation :

It's not possible in this case so return -1.

My code:

As we need to find the smallest M, I am selecting only the elements from 0 to n-2

public int process(int[] arr) {
    int answer = 1;
    for(int i=0; i<arr.length-1; i  ) {
        answer *= arr[i];
    }
    return answer;
}

This program works for these 2 sample test cases but it was failing for multiple hidden test cases. I trying to understand what I am missing here.

CodePudding user response：

The way you implemented process() assumes the input array is sorted. But anyway, I don't think sorting will help here. Note that the number satisfying the given conditions can be divided by the biggest number. For [2, 3, 5, 6] it is 6. Dividing the product of all the elements by consecutive elements from the biggest to the lowest and stopping at the first that is not a divisor is also not correct. In the example [2, 4, 5, 6] this would give 2 * 4 * 5 = 40 when the correct answer is 20.

My idea is to use an algorithm inspired by Sieve of Eratosthenes. Note that the number that satisfies the conditions can't be bigger than the product of all the elements. So create a table divisors[] with indices from 0 through the product of the elements of array where divisors[i] indicates how many elements from array divide i. Iterate over elements of array and increment all elements in divisors[i] where i is divided by the element. Then find the first i for which divisors[i] == n - 1.

The limitation is that divisors can be quite big depending on what is the product of array, so applicability will be limited to relatively small values in array.

CodePudding user response：

Try this code:

public int process(int[] arr) {
    int prod = array[0]
    for(int i=1; i<arr.length; i  ) {
      prod *= arr[i];
    }
    int answer = prod;
    int answer_partial;
    for(int i=0; i<arr.length; i  ) {
      answer_partial = (int)(prod/arr[i]);
      if ((answer_partial % arr[i]) != 0) {
        if (answer_partial < answer) {
            answer = answer_partial;
        }
    }
    if (answer == prod) {
      answer = -1;
    }
    return answer;
}

Sorry I can't test it now. I convert from Python but I don't have a Java Environment in my system.

I have test the algoritm with this example:

[6, 30, 5, 3] ---> answer = -1
[1, 2, 3]     ---> answer = 2 (1*2)
[1, 2, 3, 3]  ---> answer = 9 (1*3*3)
[9, 14, 21]   ---> answer = 189 (9*21)
[6, 7, 5, 3]  ---> answer = 90 (3*5*6) <-- As says @Portal is not correct.

The program is able only to find the group of N-1 number but after that it is necessary to calculate the lower common multiple of this.