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 :
6
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：
Calculation of the Least Common Multiple (LCM)
A problem inside the task is the calculation of the Least Common Multiple of 2 numbers. The method public int lowerCommonMultiple(int x1, int x2) solves this problem and I think it can be used in other context.
List of the class methods
All the code is included in the methods of the BestMultiple class. These methods (excluding the main) are:
public int[] removeElem(int[] tensArray, int rm_index): used to remove an element from an arraypublic int leastCommonMultiple(int x1, int x2): calculates the Least Common Multiple of 2 numbersprivate int getLeastCommonMultipleNnumber(int[] arr): Calculates the least common multiple of N-1 integer contain in an arraypublic int process(int[] arr): calculates the least multiple of exactly N-1 number of an array of N integer; it manages many test strange cases (array empty, elem<=0, etc.)
May be the code is not optimized, but I hope it is correct (the output added, shows that it works correctly, at least with the test cases chosen).
public class BestMultiple {
/*
Method: removeElem() remove an element from
an array.
*/
public int[] removeElem(int[] tensArray, int rm_index) {
// Create a proxy array of size one less than original array
int[] proxyArray = new int[tensArray.length - 1];
// copy all the elements in the original to proxy array
// except the one at index
for (int i = 0, k = 0; i < tensArray.length; i ) {
// check if index is crossed, continue without copying
if (i == rm_index) {
continue;
}
// else copy the element
proxyArray[k ] = tensArray[i];
}
return proxyArray;
}
/*
Method: leastCommonMultiple() Calculates the Least Common
multiple for 2 numbers
*/
public int leastCommonMultiple(int x1, int x2) {
int lcm = 1;
int max = x1;
if ((x1 == 0) || (x2 == 0)) {
lcm = 0;
} else {
if (x2 > x1) {
max = x2;
}
for (int i = 2; i <= max; i ) {
int exp_x1 = 0;
int exp_x2 = 0;
int exp = 0;
if (x1 > 1) {
while ((x1 % i) == 0) {
exp_x1 ;
x1 /= i;
}
}
if (x2 > 1) {
while ((x2 % i) == 0) {
exp_x2 ;
x2 /= i;
}
}
if ((exp_x1 > 0) || (exp_x2 > 0)) {
exp = exp_x1;
if (exp_x2 > exp) {
exp = exp_x2;
}
while (exp > 0) {
lcm *= i;
exp--;
}
}
}
}
return lcm;
}
/*
Method: getLeastCommonMultipleNnumber()
Calculates the least common multiple of N-1
integer contain in an array
*/
public int getLeastCommonMultipleNnumber(int[] arr) {
int multiple = 1;
if (arr.length >= 2) {
multiple = leastCommonMultiple(arr[0], arr[1]);
for (int j = 2; j < arr.length; j ) {
multiple = leastCommonMultiple(multiple, arr[j]);
}
} else {
// array with only 2 elements
multiple = arr[0];
}
return multiple;
}
/*
Method: process()
Calculates the least multiple of EXACTLY N-1
number of an array of N integer
*/
public int process(int[] arr) {
int answer;
if (arr.length <= 1) {
// array contains only one element or is empty => return -1
answer = -1;
} else {
int pos_elem_zero = -1;
int prod = 1;
for (int i = 0; i < arr.length; i ) {
if (arr[i] > 0) {
prod *= arr[i];
} else {
if (arr[i] < 0) {
// integer < 0 are not allowed
return -1;
}
if (pos_elem_zero == -1) {
pos_elem_zero = i;
} else {
// there are more element == 0
return -1;
}
}
}
if (pos_elem_zero >= 0) {
// there is one element == 0
arr = this.removeElem(arr, pos_elem_zero);
return getLeastCommonMultipleNnumber(arr);
}
// managing of normal test case
answer = prod;
for (int i = 0; i < arr.length; i ) {
int elem = arr[i];
int[] arr2 = this.removeElem(arr, i);
int multiple = getLeastCommonMultipleNnumber(arr2);
if (multiple > elem) {
if ((multiple % elem) != 0) {
if (multiple < answer) {
answer = multiple;
}
}
} else {
if (multiple < elem) {
answer = multiple;
}
}
}
if (answer == prod) {
answer = -1;
}
}
return answer;
}
/*
Method: main() Executes test of process()
method
*/
public static void main(String[] args) {
BestMultiple bm = new BestMultiple();
int[] arr1 = {6,30,5,3};
int[] arr2 = {1,2,3};
int[] arr3 = {1,2,3,3};
int[] arr4 = {6,7,5,3};
int[] arr5 = {9,14, 21};
int[] arr6 = {2,4};
int[] arr7 = {2,3,5};
int[] arr8 = {2,3,6};
int[] arr9 = {2};
int[] arr10 = {};
int[] arr11 = {2,3,0};
int[] arr12 = {0,2,3,0};
int[] arr13 = {20,3};
int[] arr14 = {0,6,15};
int[] arr15 = {1,6,15,-1};
int[] arr16 = {1,6,15};
int[] arr17 = {2,3,0,6,15};
System.out.println("{6,30,5,3} --> " bm.process(arr1));
System.out.println("{1,2,3} --> " bm.process(arr2));
System.out.println("{1,2,3,3} --> " bm.process(arr3));
System.out.println("{6,7,5,3} --> " bm.process(arr4));
System.out.println("{9,14,21} --> " bm.process(arr5));
System.out.println("{2,4} --> " bm.process(arr6));
System.out.println("{2,3,5} --> " bm.process(arr7));
System.out.println("{2,3,6} --> " bm.process(arr8));
System.out.println("{2} --> " bm.process(arr9));
System.out.println("{} --> " bm.process(arr10));
System.out.println("{2,3,0} --> " bm.process(arr11));
System.out.println("{0,2,3,0} --> " bm.process(arr12));
System.out.println("{20,3} --> " bm.process(arr13));
System.out.println("{0,6,15} --> " bm.process(arr14));
System.out.println("{1,6,15,-1} --> " bm.process(arr15));
System.out.println("{1,6,15} --> " bm.process(arr16));
System.out.println("{2,3,0,6,15} --> " bm.process(arr17));
}
}
Output of the program
The output of the program with the test cases chosen is:
{6,30,5,3} --> -1
{1,2,3} --> 2
{1,2,3,3} --> 3
{6,7,5,3} --> 30
{9,14,21} --> 42
{2,4} --> 2
{2,3,5} --> 6
{2,3,6} --> -1
{2} --> -1
{} --> -1
{2,3,0} --> 6
{0,2,3,0} --> -1
{20,3} --> 3
{0,6,15} --> 30
{1,6,15,-1} --> -1
{1,6,15} --> 6
{2,3,0,6,15} --> 30
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：
You start by writing a method process that computes the minimum number for each subarray with one element excluded:
public static int process(int... arr) {
int min = -1;
for (int i = 0; i < arr.length; i) {
int r = process(arr, i);
if (r != -1) {
if (min == -1) {
min = r;
} else {
min = Math.min(min, r);
}
}
}
return min;
}
Where the second process method looks like this:
private static int process(int[] arr, int exclude) {
int result = 0;
for (int i = 0; i < arr.length; i) {
if (i != exclude) {
if (result == 0) {
result = arr[i];
} else {
result = lcm(result, arr[i]);
}
}
}
if (result%arr[exclude] == 0) {
return -1;
}
return result;
}
You need a method that computes the LCM of two numbers. Here, I'll use a second method that computes the GCD:
private static int lcm(int a, int b) {
return a*b/gcd(a,b);
}
private static int gcd(int a, int b) {
if (a == 0) {
return b;
} else if (b == 0) {
return a;
} else {
while (a != b) {
if (a > b) {
a -= b;
} else {
b -= a;
}
}
return a;
}
}
Examples:
System.out.println(process(2, 3, 5)); // prints 6
System.out.println(process(2, 3, 6)); // prints -1
System.out.println(process(9, 14, 21)); // prints 42 (divisible by 14 and 21, but not by 9
System.out.println(process(6, 7, 5, 3)); // prints 30 (divisible by 6, 5, 3, but not by 7