An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.
For example, consider array A such that
A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.
Write a function
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.
For example, given array A such that
A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3the function may return 0, 2, 4, 6 or 7, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Solution.java:5: error: not a statement Map<Integer, List<Integer>> = new TreeMap<>(); ^ Solution.java:5: error: ';' expected Map<Integer, List<Integer>> = new TreeMap<>(); ^ Solution.java:5: error: illegal start of type Map<Integer, List<Integer>> = new TreeMap<>(); ^ Solution.java:5: error: not a statement Map<Integer, List<Integer>> = new TreeMap<>(); ^ Solution.java:5: error: ';' expected Map<Integer, List<Integer>> = new TreeMap<>(); ^ 5 errors
Solution.java:5: error: not a statement Map<Integer, List<Integer>> = new TreeMap<>(); ^ Solution.java:5: error: ';' expected Map<Integer, List<Integer>> = new TreeMap<>(); ^ Solution.java:5: error: illegal start of type Map<Integer, List<Integer>> = new TreeMap<>(); ^ Solution.java:5: error: not a statement Map<Integer, List<Integer>> = new TreeMap<>(); ^ Solution.java:5: error: ';' expected Map<Integer, List<Integer>> = new TreeMap<>(); ^ 5 errors
Solution.java:6: error: cannot find symbol return m1.size() > m2.size(); ^ symbol: method size() location: variable m1 of type Integer Solution.java:6: error: cannot find symbol return m1.size() > m2.size(); ^ symbol: method size() location: variable m2 of type Integer 2 errors
Solution.java:6: error: cannot find symbol return m1.size() - m2.size(); ^ symbol: method size() location: variable m1 of type Integer Solution.java:6: error: cannot find symbol return m1.size() - m2.size(); ^ symbol: method size() location: variable m2 of type Integer 2 errors
Solution.java:6: error: package Systeme does not exist Systeme.out.println(m1); ^ Solution.java:7: error: cannot find symbol return m1.size() - m2.size(); ^ symbol: method size() location: variable m1 of type Integer Solution.java:7: error: cannot find symbol return m1.size() - m2.size(); ^ symbol: method size() location: variable m2 of type Integer 3 errors
Solution.java:7: error: cannot find symbol return m1.size() - m2.size(); ^ symbol: method size() location: variable m1 of type Integer Solution.java:7: error: cannot find symbol return m1.size() - m2.size(); ^ symbol: method size() location: variable m2 of type Integer 2 errors
Solution.java:5: error: incompatible types: cannot infer type arguments for TreeMap<> Map<Integer, List<Integer>> treeMap = new TreeMap<>((List l1, List l2) -> { ^ reason: inference variable K has incompatible bounds equality constraints: Integer upper bounds: List,Object where K is a type-variable: K extends Object declared in class TreeMap 1 error
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.getOrDefault(A[i], new ArrayList<Integer>()).add(A[i]);
if () {
dominator = ;
break;
}
}
return dominator;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.getOrDefault(A[i], new ArrayList<Integer>()).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return dominator;
}
}
Exception in thread "main" java.lang.NullPointerException at Solution.solution(Solution.java:10) at Exec.run(exec.java:46) at Exec.main(exec.java:31)
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.getOrDefault(A[i], new ArrayList<Integer>())
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return dominator;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.contains(A[i])) {
map.
}
map.getOrDefault(A[i], new ArrayList<Integer>())
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return dominator;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.contains(A[i])) {
map.put(A[i], new ArrayList<Integer>()));
}
map.getOrDefault(A[i], new ArrayList<Integer>())
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return dominator;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.contains(A[i])) {
map.put(A[i], new ArrayList<Integer>()));
}
map.get(A[i]).add(A[i]Integer>())
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return dominator;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.contains(A[i])) {
map.put(A[i], new ArrayList<Integer>()));
}
map.get(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return dominator;
}
}
Solution.java:10: error: ';' expected map.put(A[i], new ArrayList<Integer>())); ^ 1 error
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.contains(A[i])) {
map.put(A[i], new ArrayList<Integer>());
}
map.get(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return dominator;
}
}
Solution.java:9: error: cannot find symbol if (!map.contains(A[i])) { ^ symbol: method contains(int) location: variable map of type Map<Integer,List<Integer>> 1 error
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.containsKeu(A[i])) {
map.put(A[i], new ArrayList<Integer>());
}
map.get(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return dominator;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.containsKey(A[i])) {
map.put(A[i], new ArrayList<Integer>());
}
map.get(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return dominator;
}
}
example test
got 3, but element is not a dominator, value 2 has only 1 occurences (n=8)
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.containsKey(A[i])) {
map.put(A[i], new ArrayList<Integer>());
}
map.get(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return map.dominator;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, List<Integer>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.containsKey(A[i])) {
map.put(A[i], new ArrayList<Integer>());
}
map.get(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Int>> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
if (!map.containsKey(A[i])) {
map.put(A[i], new ArrayList<Integer>());
}
map.get(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
}
map.get(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i]).add(A[i]);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i], i);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i], );
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i], map.get(A[i]++);
if (map.get(A[i]).size() > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i], map.get(A[i]++);
if (map.get(A[i]) > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
Solution.java:9: error: ')' expected map.push(A[i], map.get(A[i]++); ^ 1 error
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i], map.get(A[i]++));
if (map.get(A[i]) > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
Solution.java:5: error: incompatible types: cannot infer type arguments for HashSet<> Map<Integer, Integer> map = new HashSet<>(); ^ reason: no instance(s) of type variable(s) E exist so that HashSet<E> conforms to Map<Integer,Integer> where E is a type-variable: E extends Object declared in class HashSet Solution.java:9: error: cannot find symbol map.push(A[i], map.get(A[i]++)); ^ symbol: method push(int,Integer) location: variable map of type Map<Integer,Integer> 2 errors
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i], map.get(A[i])++);
if (map.get(A[i]) > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
Solution.java:5: error: incompatible types: cannot infer type arguments for HashSet<> Map<Integer, Integer> map = new HashSet<>(); ^ reason: no instance(s) of type variable(s) E exist so that HashSet<E> conforms to Map<Integer,Integer> where E is a type-variable: E extends Object declared in class HashSet Solution.java:9: error: unexpected type map.push(A[i], map.get(A[i])++); ^ required: variable found: value 2 errors
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i], map.get(A[i]) +);
if (map.get(A[i]) > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i], map.get(A[i]) + 1);
if (map.get(A[i]) > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
Solution.java:5: error: incompatible types: cannot infer type arguments for HashSet<> Map<Integer, Integer> map = new HashSet<>(); ^ reason: no instance(s) of type variable(s) E exist so that HashSet<E> conforms to Map<Integer,Integer> where E is a type-variable: E extends Object declared in class HashSet Solution.java:9: error: cannot find symbol map.push(A[i], map.get(A[i]) + 1); ^ symbol: method push(int,int) location: variable map of type Map<Integer,Integer> 2 errors
import java.util.*;
class Solution {
public int solution(int[] A) {
Set<Integer, Integer> set = new HashSet<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
set.push(A[i], set.get(A[i]) + 1);
if (set.get(A[i]) > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Set<Integer, Integer> set = new HashSet<>();
int dominatorIndex = -1;
for (int i=0; i<A.length; i++) {
set.push(A[i], set.get(A[i]) + 1);
if (set.get(A[i]) > A.length / 2) {
dominator = A[i];
break;
}
}
return map.get(dominator);
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Set<Integer, Integer> set = new HashSet<>();
int dominatorIndex = -1;
for (int i=0; i<A.length; i++) {
set.push(A[i], set.get(A[i]) + 1);
if (set.get(A[i]) > A.length / 2) {
dominatorIndex = i;
break;
}
}
return map.get(dominator);
}
}
Solution.java:5: error: wrong number of type arguments; required 1 Set<Integer, Integer> set = new HashSet<>(); ^ Solution.java:16: error: cannot find symbol return map.get(dominator); ^ symbol: variable dominator location: class Solution Solution.java:16: error: cannot find symbol return map.get(dominator); ^ symbol: variable map location: class Solution 3 errors
import java.util.*;
class Solution {
public int solution(int[] A) {
Set<Integer, Integer> set = new HashSet<>();
int dominatorIndex = -1;
for (int i=0; i<A.length; i++) {
set.push(A[i], set.get(A[i]) + 1);
if (set.get(A[i]) > A.length / 2) {
dominatorIndex = i;
break;
}
}
return dominatorIndex;
}
}
Solution.java:5: error: wrong number of type arguments; required 1 Set<Integer, Integer> set = new HashSet<>(); ^ 1 error
import java.util.*;
class Solution {
public int solution(int[] A) {
<Integer, Integer> set = new HashSet<>();
int dominatorIndex = -1;
for (int i=0; i<A.length; i++) {
set.push(A[i], set.get(A[i]) + 1);
if (set.get(A[i]) > A.length / 2) {
dominatorIndex = i;
break;
}
}
return dominatorIndex;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> set = new HashSet<>();
int dominatorIndex = -1;
for (int i=0; i<A.length; i++) {
set.push(A[i], set.get(A[i]) + 1);
if (set.get(A[i]) > A.length / 2) {
dominatorIndex = i;
break;
}
}
return dominatorIndex;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashMap<>();
int dominatorIndex = -1;
for (int i=0; i<A.length; i++) {
map.push(A[i], map.get(A[i]) + 1);
if (map.get(A[i]) > A.length / 2) {
dominatorIndex = i;
break;
}
}
return dominatorIndex;
}
}
Solution.java:9: error: cannot find symbol map.push(A[i], map.get(A[i]) + 1); ^ symbol: method push(int,int) location: variable map of type Map<Integer,Integer> 1 error
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashMap<>();
int dominatorIndex = -1;
for (int i=0; i<A.length; i++) {
map.put(A[i], map.get(A[i]) + 1);
if (map.get(A[i]) > A.length / 2) {
dominatorIndex = i;
break;
}
}
return dominatorIndex;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashMap<>();
int dominatorIndex = -1;
for (int i=0; i<A.length; i++) {
map.put(A[i], map.get(A[i]) + 1);
if (map.get(A[i]) > A.length / 2) {
dominatorIndex = i;
break;
}
}
return dominatorIndex;
}
}
Exception in thread "main" java.lang.NullPointerException at Solution.solution(Solution.java:9) at Exec.run(exec.java:46) at Exec.main(exec.java:31)
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashMap<>();
int dominatorIndex = -1;
for (int i=0; i<A.length; i++) {
map.put(A[i], map.getOrDefault(A[i], 0) + 1);
if (map.get(A[i]) > A.length / 2) {
dominatorIndex = i;
break;
}
}
return dominatorIndex;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashMap<>();
int domi = -1;
for (int i=0; i<A.length; i++) {
map.put(A[i], map.getOrDefault(A[i], 0) + 1);
if (map.get(A[i]) > A.length / 2) {
dominatorIndex = i;
break;
}
}
return dominatorIndex;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.put(A[i], map.getOrDefault(A[i], 0) + 1);
if (map.get(A[i]) > A.length / 2) {
dominator = i;
break;
}
}
return dominator;
}
}
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> map = new HashMap<>();
int dominator = -1;
for (int i=0; i<A.length; i++) {
map.put(A[i], map.getOrDefault(A[i], 0) + 1);
if (map.get(A[i]) > A.length / 2) {
dominator = i;
break;
}
}
return dominator;
}
}
The solution obtained perfect score.