1533. Find the Index of the Large Integer
We have an integer array arr
, where all the integers in arr
are equal except for one integer which is larger than the rest of the integers. You will not be given direct access to the array, instead, you will have an API ArrayReader
which have the following functions:
int compareSub(int l, int r, int x, int y)
: where0 <= l, r, x, y < ArrayReader.length()
,l <= r and
x <= y
. The function compares the sum of sub-arrayarr[l..r]
with the sum of the sub-arrayarr[x..y]
and returns:- 1 if
arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y]
. - 0 if
arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y]
. - -1 if
arr[l]+arr[l+1]+...+arr[r] < arr[x]+arr[x+1]+...+arr[y]
.
- 1 if
int length()
: Returns the size of the array.
You are allowed to call compareSub()
20 times at most. You can assume both functions work in O(1)
time.
Return the index of the array arr
which has the largest integer.
Follow-up:
- What if there are two numbers in
arr
that are bigger than all other numbers? - What if there is one number that is bigger than other numbers and one number that is smaller than other numbers?
Example 1:
Input: arr = [7,7,7,7,10,7,7,7] Output: 4 Explanation: The following calls to the API reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]). Thus we know that arr[0] and arr[1] doesn't contain the largest element. reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3]. reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array. Notice that we made only 3 calls, so the answer is valid.
Example 2:
Input: nums = [6,6,12] Output: 2
Constraints:
2 <= arr.length <= 5 * 10^5
1 <= arr[i] <= 100
- All elements of
arr
are equal except for one element which is larger than all other elements.
Rust Solution
struct Solution;
use std::cmp::Ordering::*;
struct ArrayReader {
n: usize,
small: i32,
diff: i32,
index: usize,
}
impl ArrayReader {
fn new(arr: Vec<i32>) -> Self {
let n = arr.len();
let small = arr[0].min(arr[1]);
let mut diff = 0;
let mut index = 0;
for i in 0..n {
if arr[i] > small {
diff = arr[i] - small;
index = i;
break;
}
}
ArrayReader {
n,
small,
diff,
index,
}
}
#[allow(non_snake_case)]
fn compareSub(&self, l: i32, r: i32, x: i32, y: i32) -> i32 {
let i = self.index as i32;
let s1 = (r - l + 1) * self.small + if l <= i && i <= r { self.diff } else { 0 };
let s2 = (y - x + 1) * self.small + if x <= i && i <= y { self.diff } else { 0 };
match s1.cmp(&s2) {
Equal => 0,
Greater => 1,
Less => -1,
}
}
fn length(&self) -> i32 {
self.n as i32
}
}
impl Solution {
pub fn get_index(reader: &ArrayReader) -> i32 {
let n = reader.length();
let mut l = 0;
let mut r = n - 1;
while l < r {
let w = r - l + 1;
let m = l + w / 2;
if w % 2 == 0 {
let cmp = reader.compareSub(l, m - 1, m, r);
if cmp == 1 {
r = m - 1;
} else {
l = m;
}
} else {
let cmp = reader.compareSub(l, m - 1, m + 1, r);
if cmp == 0 {
return m;
}
if cmp == 1 {
r = m - 1;
} else {
l = m + 1;
}
}
}
l
}
}
#[test]
fn test() {
// let arr = vec![7, 7, 7, 7, 10, 7, 7, 7];
// let reader = ArrayReader::new(arr);
// let res = 4;
// assert_eq!(Solution::get_index(&reader), res);
// let arr = vec![6, 6, 12];
// let reader = ArrayReader::new(arr);
// let res = 2;
// assert_eq!(Solution::get_index(&reader), res);
let arr = vec![1, 1, 1, 1, 1, 1, 2, 1, 1];
let reader = ArrayReader::new(arr);
let res = 6;
assert_eq!(Solution::get_index(&reader), res);
}
Having problems with this solution? Click here to submit an issue on github.