将 Array 分成 2 个子数组并检查乘法是否相等 [英] Divide Array to 2 sub arrays and check if the multiplication are equal

问题描述

我练习 Java 考试.我今天面临的问题之一是:给定一个包含 n 个数字的数组，我需要检查是否有 2 个子数组(不必相等)它们的乘法相等 - 如果有，将返回 true，否则返回 false.例如 :如果数组是:{2,15,3,4,2,5} - 将返回 True如果数组是:{2,4,6,2,3,4} - 将返回 False.

I practice for an exam in Java. One of the questions I faced today is: Given an array with n numbers, I need to check if there are 2 subarrays(doesn't have to be equal) that their multiplication equals - if there are, will return true, else false. for example : if the array is : {2,15,3,4,2,5} - will return True if the array is : {2,4,6,2,3,4} - will return False.

答案必须是递归的，没有任何循环.

the answer must be recursive, without any loops.

所以我认为如果有 2 个子数组的乘法相等，则意味着整个数组的总乘法必须是平方根数.例如，在第一个数组中，它是 3600，即 60.

so I thought that if there are 2 sub arrays that their multiplication equal it means that the total multiplication of the whole array must be a square root number. for example at the first array, it's 3600 which is 60.

到目前为止，我找不到任何不适用的情况，但仍不确定它是否 100% 会涵盖所有可能的情况.

So far I couldn't find any case that it won't work for, but still not sure 100% that it will cover all the possible cases.

这是我的代码:

    public static boolean splitEqualMult(int[] a) {
      double multi = isArrSqrt(a,0);

      if(Math.sqrt(multi) == Math.floor(Math.sqrt(multi))) {
          return true;
    }

    return false;
}

private static double isArrSqrt(int[] a, int i) {

    if(i == a.length) {
        return 1;
    }

    return a[i] * isArrSqrt(a,i+1);
}

想听听您的想法！

推荐答案

您的解决方案会产生误报.例如，数组 {2,8} 不能分成相等乘积的两个子数组，但你会返回 true，因为 2* 的平方根8 是 4.

Your solution gives false positives. For example, the array {2,8} cannot be divided into two sub-arrays of equal product, but you'll return true, since the square root of 2*8 is 4.

当您尝试解决这样的递归时，您应该考虑将输入的大小减少 1 会发生什么.

When you try to solve such a recursion you should try to think what happens if you reduce the size of the input by 1.

假设给定的数组 arr 有一个有效的分割(分成两个具有相等乘积的子组).这意味着如果删除第一个元素 a[0]，则必须能够将数组的其余部分拆分为两个子组，使得 p1 == p2 * a[0] 或 p1 == p2/a[0]，其中 p1 是第一组元素与 p2 的乘积> 是第二组元素的乘积.

Suppose a given array arr has a valid split (into two sub-groups having equal product). This means that if you remove the first element a[0], you must be able to split the rest of the array into two sub-groups such that p1 == p2 * a[0] or p1 == p2 / a[0], where p1 is the product of the elements of the first group and p2 is the product of the elements of the second group.

这表明递归方法应该检查输入数组的给定尾部(即 arr[from]...arr[arr.length-1] for some from >= 0)是否存在分裂为两个组，使得第一组的乘积除以第二组的乘积(反之亦然)等于给定因子:

This suggests that the recursive method should check whether for a given tail of the input array (i.e. arr[from]...arr[arr.length-1] for some from >= 0), there exists a split into two groups such that the product of the first group divided by the product of the second group (or vice versa) equals a given factor:

public static boolean canSplit(int[] arr, int from, double factor)
{
    if (from == arr.length - 1) {
        return arr[from] == factor;
    }
    return canSplit(arr, from + 1, factor * arr[from]) || canSplit(arr, from + 1, factor / arr[from]);
}

初始调用将是:

public static boolean canSplit(int[] arr)
{
    if (arr.length < 2) {
        return false;
    } else {
        return canSplit(arr, 0, 1); // the second parameter is 0, since the first recursive call
                                    // applies to the whole array
                                    // the third parameter is 1, since we want to check if there 
                                    // are two groups such that the product of the first divided
                                    // by the product of the second is 1 (i.e. the two products
                                    // are equal)
    }
}

测试:

System.out.println (canSplit(new int[]{2,15,3,4,2,5}));
System.out.println (canSplit(new int[]{2,4,6,2,3,4}));
System.out.println (canSplit(new int[]{2,2,4}));
System.out.println (canSplit(new int[]{2,8}));

输出:

true
false
true
false

这篇关于将 Array 分成 2 个子数组并检查乘法是否相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！