Get Outlier Value (Amazon London)

Problem Overview

• Given an array of n integers containing n−2 original numbers and their sum, identify any numbers that are neither originals nor the sum, and return the greatest outlier.
• Input: arr[n]; Output: int outlier; constraints: 3 ≤ n ≤ 1e5, 1 ≤ arr[i] ≤ 1e9; answer exists.
• Context: Prototype AWS outlier detection service for arrays.
• Company: Amazon London; asked in Amazon interviews; a coding interview problem and common interview question.