java - 如何改进算法以获得相乘等于一系列数字之和的数字对？

Question

我正在做以下编程练习:Is my friend cheating? 。声明如下:

A friend of mine takes a sequence of numbers from 1 to n (where n > 0). Within that sequence, he chooses two numbers, a and b. He says that the product of a and b should be equal to the sum of all numbers in the sequence, excluding a and b. Given a number n, could you tell me the numbers he excluded from the sequence?

The function takes the parameter: n (n is always strictly greater than 0) and returns an array or a string (depending on the language) of the form:

[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or or [{a, b}, ...]

with all (a, b) which are the possible removed numbers in the sequence 1 to n.

[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or ...will be sorted in increasing order of the "a".

It happens that there are several possible (a, b). The function returns an empty array (or an empty string) if no possible numbers are found which will prove that my friend has not told the truth! (Go: in this case return nil).

Examples:

removeNb(26) should return [[15, 21], [21, 15]]

这个想法是:

Calculate sum of 1..n
For each number a
 For each number b
  if a*b=sum-(a+b)
   add to result

我编写了以下代码:

import java.util.*;
import java.util.stream.*;

public class RemovedNumbers {
    public static List<long[]> removNb(long n) {
    System.out.println("n: "+n);
    long sum = LongStream.rangeClosed(1,n).sum();
    List<long[]> result = new ArrayList<>();
    System.out.println("sum: "+sum);
    for(int a = 1; a <= n && a <= sum; a++){
      System.out.println("a: "+a);
      long prodMax = a*n;
      long sumMax = sum-(a+n);
      if(prodMax < sumMax){
        System.out.println("prodMax: "+prodMax);
        System.out.println("sumMax: "+sumMax);
        continue;
      };
      for(int b = 1; b <= n && a*b <= (sum-(a+b)); b++){
        if(a==b) continue;
        System.out.println("b: "+b);
        if(a*b == sum-(a+b)){
          result.add(new long[]{a,b});
          System.out.println("result: "+Arrays.deepToString(result.toArray()));
        }    
      }
    }
    System.out.println("result: "+Arrays.deepToString(result.toArray()));
    return result;
    }
}

它通过了以下测试:

import static org.junit.Assert.*;
import java.util.List;
import java.util.ArrayList;
import org.junit.Test;

public class RemovedNumbersTest {
  @Test
    public void test12() {
        List<long[]> res = new ArrayList<long[]>();
        res.add(new long[] {15, 21});
        res.add(new long[] {21, 15});
        List<long[]> a = RemovedNumbers.removNb(26);
        assertArrayEquals(res.get(0), a.get(0));
        assertArrayEquals(res.get(1), a.get(1));
    }
    @Test
    public void test14() {
        List<long[]> res = new ArrayList<long[]>();
        List<long[]> a = RemovedNumbers.removNb(100);
        assertTrue(res.size() == a.size());
    }
}

例如，对于 test12，跟踪为:

n: 26
sum: 351
a: 1
prodMax: 26
sumMax: 324
a: 2
prodMax: 52
sumMax: 323
a: 3
prodMax: 78
sumMax: 322
a: 4
prodMax: 104
sumMax: 321
a: 5
prodMax: 130
sumMax: 320
a: 6
prodMax: 156
sumMax: 319
a: 7
prodMax: 182
sumMax: 318
a: 8
prodMax: 208
sumMax: 317
a: 9
prodMax: 234
sumMax: 316
a: 10
prodMax: 260
sumMax: 315
a: 11
prodMax: 286
sumMax: 314
a: 12
prodMax: 312
sumMax: 313
a: 13
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 14
b: 15
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
b: 22
b: 23
b: 24
a: 14
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 15
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
b: 22
a: 15
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 16
b: 17
b: 18
b: 19
b: 20
b: 21
result: [[15, 21]]
a: 16
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 17
b: 18
b: 19
a: 17
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
b: 18
a: 18
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
b: 17
a: 19
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
b: 16
a: 20
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
a: 21
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
b: 15
result: [[15, 21], [21, 15]]
a: 22
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
b: 14
a: 23
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
a: 24
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
b: 13
a: 25
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
a: 26
b: 1
b: 2
b: 3
b: 4
b: 5
b: 6
b: 7
b: 8
b: 9
b: 10
b: 11
b: 12
result: [[15, 21], [21, 15]]

但是当输入很大的数字时，例如n=1000003，就会超时(执行时间大于16000ms)。

我还读过:

• Fill arrays with ranges of numbers
• How to sum a list of integers with java streams?

我们如何改进这个算法？

Answer 1

您无需遍历该对中的第二个数字。您只能迭代第一个数字对并计算第二个数字。如果x是第一个数字(您迭代它)，y是第二个数字(您想要找到它)，s是所有数字的总和，那么你只需要解这个方程:

x * y = s - x - y    <=>

(x + 1) * y = s - x    <=>

y = (s - x) / (x + 1)

因此，如果 (s - x)/(x + 1) 是整数且不等于 x，则它是成对的第二个数字。

通过此更改，您的算法将在 O(n) 时间内运行，而不是 O(n^2)。