查找给定范围内n个数的倍数

Question

我遇到了一个问题，我给了一个范围：考虑：start, end

和N号码：n1,n2,n3....nn

我应该找到范围内所有N个数的倍数（开始，结束）

我试过的 -

我已经尝试创建一个HashSet，然后在范围start，end（在hashset中插入每个多个）中逐个找到N个数的倍数。然后在集合的最后大小是答案。

这有效。但不适合大输入。

考虑-

Input: 1 10 3 6 3 7
Output: 4

说明-

Range: 1 to 10
N: 3
Numbers: 6, 3, 7
Multiples of 3 = 3,6,9 (quantity =3)
Multiples of 6 =6 (quantity =1, but 6 is common)
Multiples of 7 = 7 (quantity=1)
Total quantity = 4

因此输出为4.输出为4而不是5，因为6是3,6的倍数。 （避免重复）。

Answer 1

一个简单的答案就是这个：

public static void main(String[] args)
{
    /* Initialization */
    int min = 1;
    int max = 1000;
    final Set<Integer> solutions = new HashSet<>();
    final Set<Integer> items = new HashSet<>();
    Collections.addAll(items, 3,6,7);


    /* Solution */
    items.forEach(element -> solutions.addAll(findMultiples(element, min, max)));

    System.out.println("Total quantity: " + solutions.size());
    solutions.forEach(System.out::println);
}

private static Collection<Integer> findMultiples(int element, int min, int max) {
    if (min % element != 0) {
        min = element * (min / element + 1);
    }
    final Collection<Integer> solutions = new ArrayList<>();
    for (int i = min; i < max; i+=element) {
        solutions.add(i);
    }

    return solutions;
}

对于每个元素，您将查找第一个Integer，它是给定范围的倍数。然后，你用element的步骤迭代。使用你的HashSet，很容易找到结果。

Answer 2

据我所知，你有一个数字和范围列表。您想知道范围中有多少数字是列表中其中一个数字的倍数。

要解决此问题，您需要定义divisibility isDivisible和multiplicity isMultiple。请注意，我将isMultiple定义为number是否是列表units中的一个数字的倍数而不是另一个数字。

最后，您要检查您的范围中的哪些数字符合条件。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solver {
    public static void main(final String[] args) {
        final Solver solver = new Solver();
        final List<Integer> input = Arrays.asList(3, 6, 3, 7);
        final int result = solver.numberOfMultiples(1, 10, input);
        System.out.println("Result: " + result);
    }

    public int numberOfMultiples(final int start, final int end, final List<Integer> numbers) {
        final List<Integer> multiples = new ArrayList<>();
        for (int i = start; i < end; i++) {
            if (isMultiple(i, numbers)) {
                multiples.add(i);
            }
        }
        return multiples.size();
    }

    private boolean isMultiple(final int number, final List<Integer> units) {
        for (final int unit : units) {
            if (isDivisible(number, unit)) {
                return true;
            }
        }
        return false;
    }

    private boolean isDivisible(final int number, final int unit) {
        return number % unit == 0;
    }
}

Answer 3

然后在末尾减去大小范围的集合大小（end-start + 1）。为什么？

您创建的HashSet是您想要获得的实际数量。在上面的问题中，你的HashSet包含3,6,9,7。那么为什么要从初始设置大小中减去这个设置大小。简单得到set.size()。这是你的数量。

Answer 4

您可以使用以下函数非常快速地找到倍数：

public static int multiples(int lower, int upper, int divider) {
    int number = ((int) (upper / divider)) - ((int) (lower / divider));
    return number;
}

Answer 5

这是另一种带有一些测试数据的解决方案。没有HashSets是完成此任务的必要条件。

import java.util.*;

public class MultipleCount {

   public static void main(String[] args) {
      List<List<Integer>> testData = List.of(List.of(1, 10, 3, 6, 3, 7),
            List.of(32964, 73489, 587, 438, 510, 939, 833, 674, 770, 795),
            List.of(1, 10, 2, 2, 2, 2));

      for (List<Integer> list : testData) {
         System.out.println(list);
         int m = getMultiples(list);
         System.out.println(m);
      }
   }

   public static int getMultiples(List<Integer> data) {
      List<Integer> results = new ArrayList<>();

      for (int k : data.subList(2, data.size())) {
         for (int i = data.get(0); i <= data.get(1); i++) {
            int r = i;
            while (r % k == 0) {
               if (!results.contains(r)) {
                  results.add(r);
               }
               r = r / k;
            }
         }
      }
      return results.size();
   }
}