Harry and magical number
All submissions for this problem are available.
Harry and Hermione are playing a game in which Hermione challenges Harry by giving an array A and a number S, and asks to provide an efficient magical algorithm to find a number K from array A such that if all elements in A greater than K are changed to K, the sum of all elements in the resulting array will be S. Now harry has to find that magical number K. So help out harry in this task.
The first line contains an integer T, total number of testcases. Then follow T lines. First line of each test case consists of two numbers represting N and S. Second line of each test case consists of n integers represting array A.
If there exists the number K print in a new line, else print "-1" (without inverted comma). If more than one K is possible, then print the minimum one.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 2*104
- 1 ≤ S ≤ 1011
- 1 ≤ A[i] ≤ 105
- Subtask #1 [30 points]: 1 ≤ N≤ 102 & 1 ≤ S≤ 108
- Subtask #2 [70 points]: No additional constraints
Input: 1 5 15 12 3 6 7 8 Output: 3
Here if all the elements greater than 3 in the array are converted into 3 then we get the sum as 15 i.e; 12,6,7,8 are converted into 3
|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, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions