Weird Modulo Problem
All submissions for this problem are available.You are given an array $A$ of $N$ positive and pairwise distinct integers. You can permute the elements in any way you want. The cost of an ordering $(A_1, A_2, \ldots, A_N)$ is defined as $ (((A_1 \bmod A_2) \bmod A_3)......) \bmod A_N$ where $X \bmod Y$ means the remainder when $X$ is divided by $Y$. You need to find the maximum cost which can be attained through any possible ordering of the elements. ###Input: - The first line contains $T$ denoting the number of test cases. - The first line of each testcase contains a single integer $N$. - The second line of each testcase contains $N$ space-separated integers, the elements of $A$. ###Output: - For each testcase, output the maximum possible cost in a new line. ###Constraints - $1 \leq T \leq 5*10^5$ - $2 \leq N \leq 5*10^5$ - $1 \leq A_i \leq 10^9$ - Sum of $N$ over all testcases is less than or equal to $10^6$ - All elements in a single testcase are distinct. ###Subtasks - 100 points : Original constraints. ###Sample Input: ``` 1 2 7 12 ``` ###Sample Output: ``` 7 ``` ###Explanation: The two possible ways to order the elements are [7, 12] and [12, 7]. In the first case, the cost is $7 \bmod 12 = 7$ and in the second case the cost is $12 \bmod 7 = 5$. Clearly the answer is 7.
|Tags||cakewalk, expp2019, shashwatchandr|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.