Description
We have an integer array nums, where all the integers in nums are 0 or 1. You will not be given direct access to the array, instead, you will have an API ArrayReader which have the following functions:
You are allowed to call query() 2 * n times at most where n is equal to ArrayReader.length().
Return any index of the most frequent value in nums, in case of tie, return -1.
Example 1:
Input: nums = [0,0,1,0,1,1,1,1]
Output: 5
Explanation: The following calls to the API
reader.length() // returns 8 because there are 8 elements in the hidden array.
reader.query(0,1,2,3) // returns 2 this is a query that compares the elements nums[0], nums[1], nums[2], nums[3]
// Three elements have a value equal to 0 and one element has value equal to 1 or viceversa.
reader.query(4,5,6,7) // returns 4 because nums[4], nums[5], nums[6], nums[7] have the same value.
we can infer that the most frequent value is found in the last 4 elements.
Index 2, 4, 6, 7 is also a correct answer.
Example 2:
Input: nums = [0,0,1,1,0]
Output: 0
Example 3:
Input: nums = [1,0,1,0,1,0,1,0]
Output: -1
Constraints:
5 <= nums.length <= 1050 <= nums[i] <= 1
Follow up: What is the minimum number of calls needed to find the majority element?
Solutions
Solution 1: Brainteaser
We first call reader.query(0, 1, 2, 3) and record the result as x.
Next, we iterate from index 4 onwards. Each time we call reader.query(0, 1, 2, i), if the result is the same as x, we increment a by one; otherwise, we increment b by one and update k to i.
Then, we need to check whether the elements at indices 0, 1, 2 are the same as the element at index 3. If they are the same, we increment a by one; otherwise, we increment b by one and update k to the corresponding index.
Finally, if a = b, it means the number of 0s and 1s in the array are equal, so we return -1; otherwise, if a > b, we return 3, otherwise we return k.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
PythonJavaC++GoTypeScript
# """
# This is the ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
# class ArrayReader(object):
# # Compares 4 different elements in the array
# # return 4 if the values of the 4 elements are the same (0 or 1).
# # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
# # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
# def query(self, a: int, b: int, c: int, d: int) -> int:
#
# # Returns the length of the array
# def length(self) -> int:
#
class Solution:
def guessMajority(self, reader: "ArrayReader") -> int:
n = reader.length()
x = reader.query(0, 1, 2, 3)
a, b = 1, 0
k = 0
for i in range(4, n):
if reader.query(0, 1, 2, i) == x:
a += 1
else:
b += 1
k = i
y = reader.query(0, 1, 2, 4)
if reader.query(1, 2, 3, 4) == y:
a += 1
else:
b += 1
k = 0
if reader.query(0, 2, 3, 4) == y:
a += 1
else:
b += 1
k = 1
if reader.query(0, 1, 3, 4) == y:
a += 1
else:
b += 1
k = 2
if a == b:
return -1
return 3 if a > b else k(code-box)
/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* interface ArrayReader {
* public:
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or
* vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal
* to 1. public int query(int a, int b, int c, int d);
*
* // Returns the length of the array
* public int length();
* };
*/
class Solution {
public int guessMajority(ArrayReader reader) {
int n = reader.length();
int x = reader.query(0, 1, 2, 3);
int a = 1, b = 0;
int k = 0;
for (int i = 4; i < n; ++i) {
if (reader.query(0, 1, 2, i) == x) {
++a;
} else {
++b;
k = i;
}
}
int y = reader.query(0, 1, 2, 4);
if (reader.query(1, 2, 3, 4) == y) {
++a;
} else {
++b;
k = 0;
}
if (reader.query(0, 2, 3, 4) == y) {
++a;
} else {
++b;
k = 1;
}
if (reader.query(0, 1, 3, 4) == y) {
++a;
} else {
++b;
k = 2;
}
if (a == b) {
return -1;
}
return a > b ? 3 : k;
}
}(code-box)
/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* class ArrayReader {
* public:
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
* int query(int a, int b, int c, int d);
*
* // Returns the length of the array
* int length();
* };
*/
class Solution {
public:
int guessMajority(ArrayReader& reader) {
int n = reader.length();
int x = reader.query(0, 1, 2, 3);
int a = 1, b = 0;
int k = 0;
for (int i = 4; i < n; ++i) {
if (reader.query(0, 1, 2, i) == x) {
++a;
} else {
++b;
k = i;
}
}
int y = reader.query(0, 1, 2, 4);
if (reader.query(1, 2, 3, 4) == y) {
++a;
} else {
++b;
k = 0;
}
if (reader.query(0, 2, 3, 4) == y) {
++a;
} else {
++b;
k = 1;
}
if (reader.query(0, 1, 3, 4) == y) {
++a;
} else {
++b;
k = 2;
}
if (a == b) {
return -1;
}
return a > b ? 3 : k;
}
};(code-box)
/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* type ArrayReader struct {
* }
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
* func (this *ArrayReader) query(a, b, c, d int) int {}
*
* // Returns the length of the array
* func (this *ArrayReader) length() int {}
*/
func guessMajority(reader *ArrayReader) int {
n := reader.length()
x := reader.query(0, 1, 2, 3)
a, b := 1, 0
k := 0
for i := 4; i < n; i++ {
if reader.query(0, 1, 2, i) == x {
a++
} else {
b++
k = i
}
}
y := reader.query(0, 1, 2, 4)
if reader.query(1, 2, 3, 4) == y {
a++
} else {
b++
k = 0
}
if reader.query(0, 2, 3, 4) == y {
a++
} else {
b++
k = 1
}
if reader.query(0, 1, 3, 4) == y {
a++
} else {
b++
k = 2
}
if a == b {
return -1
}
if a > b {
return 3
}
return k
}(code-box)
/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* class ArrayReader {
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
* query(a: number, b: number, c: number, d: number): number { };
*
* // Returns the length of the array
* length(): number { };
* };
*/
function guessMajority(reader: ArrayReader): number {
const n = reader.length();
const x = reader.query(0, 1, 2, 3);
let a = 1;
let b = 0;
let k = 0;
for (let i = 4; i < n; ++i) {
if (reader.query(0, 1, 2, i) === x) {
++a;
} else {
++b;
k = i;
}
}
const y = reader.query(0, 1, 2, 4);
if (reader.query(1, 2, 3, 4) === y) {
++a;
} else {
++b;
k = 0;
}
if (reader.query(0, 2, 3, 4) === y) {
++a;
} else {
++b;
k = 1;
}
if (reader.query(0, 1, 3, 4) === y) {
++a;
} else {
++b;
k = 2;
}
if (a === b) {
return -1;
}
return a > b ? 3 : k;
}(code-box)
