مساله:
یکی از دوستان من دنباله ای از اعداد 1 تا n (جایی که n> 0) را می گیرد.
در آن دنباله، او دو عدد a و b را انتخاب می کند.
او می گوید حاصلضرب a و b باید برابر مجموع همه اعداد موجود در دنباله، بجز a و b باشد.
با توجه به عدد n، آیا می توانید اعدادی را که او از دنباله حذف کرده را به من بگویید؟
تابع این پارامترها را دارد: n (n همیشه بسیار بزرگتر از 0 است) و یک آرایه یا یک رشته (بسته به زبان) فرم را برمی گرداند:
[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or or [{a, b}, ...]با همه (a ، b) که ممکن است اعداد حذف شده در دنباله 1 تا n باشند.
[(a, b), …] or [[a, b], …] or {{a, b}, …} or … به ترتیب افزایش “a” مرتب می شود.
امکان اینکه چندین (a,b) وجود داشته باشد اتفاق می افتد. اگر هیچ عدد احتمالی پیدا نشود، تابع یک آرایه خالی (یا یک رشته خالی) را برمی گرداند که ثابت می کند دوست من حقیقت را نگفته است! (Go: در این حالت صفر را برمی گرداند).
مثالها:
removNb(26) should return [(15, 21), (21, 15)]
or
removNb(26) should return { {15, 21}, {21, 15} }
or
removeNb(26) should return [[15, 21], [21, 15]]
or
removNb(26) should return [ {15, 21}, {21, 15} ]
or
removNb(26) should return "15 21, 21 15"A friend of mine takes the sequence of all 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:
removNb(26) should return [(15, 21), (21, 15)]
or
removNb(26) should return { {15, 21}, {21, 15} }
or
removeNb(26) should return [[15, 21], [21, 15]]
or
removNb(26) should return [ {15, 21}, {21, 15} ]
or
removNb(26) should return "15 21, 21 15"
or
in C:
removNb(26) should return {{15, 21}{21, 15}} tested by way of strings.
Function removNb should return a pointer to an allocated array of Pair pointers, each one also allocated.
Note
See examples of returns for each language in “RUN SAMPLE TESTS”
راه حل ها (Solutions):
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.LongStream;
public class RemovedNumbers {
public static List<long[]> removNb(long n) {
// your code
long sum = n * (1 + n) / 2;
return LongStream.rangeClosed(1, n)
.filter( i -> (sum + 1) % (i + 1) == 0)
.mapToObj( i -> new long[] { i, (sum + 1) / (i + 1) - 1})
.filter( i -> i[0] != i[1] && i[1] <= n)
.collect(Collectors.toList());
}
}import java.util.ArrayList;
import java.util.List;
public class RemovedNumbers {
public static List<long[]> removNb(long n) {
List<long[]> result = new ArrayList<long[]>();
long total = (n*(n+1))/2;
for (int b=1; b <= n+1; b++) {
long a = (total-b) / (b+1);
if (a < n && a*b == total-a-b) {
result.add(new long[] {b, a});
}
}
return result;
}
}import java.util.LinkedList;
public class RemovedNumbers {
/*
We desire: ab = 1 + ... + n - a - b
Take advantage of b = sum - a
-------
a + 1
*/
public static LinkedList<long[]> removNb(long n) {
LinkedList<long[]> numbers = new LinkedList<long[]>();
long sum = (n * n + n) / 2;
for (long a = 1; a < n; a++) {
double b = (sum - a) / (double) (a + 1);
if (b <= n && b % 1 == 0) {
numbers.add(new long[] {a, (long) b});
}
}
return numbers;
}
}import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class RemovedNumbers {
public static List<long[]> removNb(long n) {
long sum = (n * n + n) / 2;
List<long[]> list = new LinkedList<>();
long halfN = n / 2;
long sqrtN = (long) Math.sqrt(n);
for (long i = halfN; i <= n - sqrtN; i++) {
long sumMinusI = (sum - i);
if ((sumMinusI % (i + 1)) == 0) {
double j = (sumMinusI / (i + 1));
list.add(new long[]{i, (long) j});
}
}
return list;
}
}import static java.util.Comparator.comparingLong;
import static java.util.stream.Collectors.toList;
import java.util.List;
import java.util.stream.LongStream;
import java.util.stream.Stream;
public class RemovedNumbers {
public static List<long[]> removNb(long n) {
// sum(1-n) = n * (n + 1) / 2
long totalSum = n * (n + 1L) / 2L;
// totalSum - (a + b) = a * b
// totalSum = (a * b) + a + b
// totalsum = ((a * b) + a + b + 1) - 1
// factorization of (a + 1) * (b + 1) = (ab + a + b + 1)
// totalSum = (a + 1) * (b + 1) - 1
// totalSum + 1 = (a + 1) * (b + 1)
long algebraicSum = totalSum + 1;
// So, find all factors such that (j * k) = algebraicSum and return pairs of {j-1, k-1}
return LongStream.rangeClosed(3, (int)Math.sqrt(algebraicSum))
//Filter for factors only
.filter(i -> algebraicSum % i == 0)
//Filter so that both factors are less than n
.filter(i -> algebraicSum / i <= n)
.boxed()
.flatMap(i -> Stream.of(new long[] { i - 1, (algebraicSum / i) - 1 },
new long[] { (algebraicSum / i) - 1, i - 1 }))
.sorted(comparingLong(arr -> arr[0]))
.collect(toList());
}
}
