BAB_I - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: akib_tonnoy
Testers: nishant403, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given an array A, find the largest integer X such that A_i \not\in [-X, X] for every i.
If no such X exists, print -1.

EXPLANATION:

First, notice that if A contains a 0, the answer is -1. This is because [-X, X] will always contain 0 for any X \geq 0.

Now, suppose a valid X existed. Looking at some A_i,

  • If A_i \gt 0, then X \lt A_i must hold.
  • If A_i \lt 0, then A_i \lt -X must hold. This is the same as saying X \lt -A_i.

So, X must be strictly less than every positive element of A, and also strictly less than the negative of every negative element of A.

This gives us a simple way to find the maximum possible X:

  • Find the smallest positive A_i in the array; let this value be P.
  • Find the largest negative A_i in the array; let this value be N.
  • The largest valid X is then \min(P, -N) - 1.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Code (Python) 
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if 0 in a: print(-1)
	else:
		minpos = 10**9
		maxneg = -10**9
		for x in a:
			if x > 0: minpos = min(minpos, x)
			else: maxneg = max(maxneg, x)
		print(min(minpos, -maxneg)-1)
2

Equivalently, print( min(map(abs,A)) - 1 ) , that is find the minimum absolute value

3

#include <bits/stdc++.h>
#define ll long long
using namespace std;

void Solve(){
int N; cin >> N;
ll A[N];
for(int i = 0; i < N; i++) cin >> A[i];
sort(A, A + N);
ll maxiNegative = A[0], minimumPositive = A[0];
bool flag = false;
for(int i = 0; i < N ; i++){
if(A[i] < 0){
maxiNegative = A[i] ;

       // 
    }
    if(A[i] >= 0){
        minimumPositive = A[i] ;
        break;
    }
  
   
}

cout << min(abs(maxiNegative), minimumPositive) - 1 << “\n”;

}

int main() {
// your code goes here

ios_base::sync_with_stdio(false);
cin.tie(NULL);

int T;
cin >> T;
while(T --){
    Solve();
}
return 0;

}

Where will this code fail ?