summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java77
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/MajorityElementTest.java61
2 files changed, 138 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java b/AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java
new file mode 100644
index 0000000..7ef3977
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/MajorityElement.java
@@ -0,0 +1,77 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.util.StringTokenizer;
+
+public class MajorityElement {
+
+ public static void main(String[] args) {
+ FastScanner scanner = new FastScanner(System.in);
+ int n = scanner.nextInt();
+ int[] a = new int[n];
+ for (int i = 0; i < n; i++) {
+ a[i] = scanner.nextInt();
+ }
+ if (getMajorityElement(a, 0, a.length -1) != -1) {
+ System.out.println(1);
+ } else {
+ System.out.println(0);
+ }
+ }
+ static class FastScanner {
+ BufferedReader br;
+ StringTokenizer st;
+
+ FastScanner(InputStream stream) {
+ try {
+ br = new BufferedReader(new InputStreamReader(stream));
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ String next() {
+ while (st == null || !st.hasMoreTokens()) {
+ try {
+ st = new StringTokenizer(br.readLine());
+ } catch (IOException e) {
+ e.printStackTrace();
+ }
+ }
+ return st.nextToken();
+ }
+
+ int nextInt() {
+ return Integer.parseInt(next());
+ }
+ }
+
+ public static int getMajorityElement(int[] a, int left, int right) {
+ if (left == right)
+ return a[left];
+ int middle = (right - left) / 2;
+ int b = getMajorityElement(a, left, left + middle);
+ int c = getMajorityElement(a, left + middle + 1, right);
+ int d = conquer(a, b, c, left, right);
+ return d;
+ }
+
+ private static int conquer(int[] a, int b, int c, int left, int right) {
+ int countB = 0;
+ int countC = 0;
+ for (int i = left; i < right + 1; i++) {
+// for (int i = 0; i < right + 1; i++) {
+ if (a[i] == b)
+ countB++;
+ if (a[i] == c)
+ countC++;
+ }
+ if (countB > (right - left + 1) / 2)
+ return b;
+ if (countC > (right - left + 1) / 2)
+ return c;
+ return -1;
+ }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/MajorityElementTest.java b/AlgoDesignAndTechniqueEdxJava/tests/MajorityElementTest.java
new file mode 100644
index 0000000..b3b1773
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/MajorityElementTest.java
@@ -0,0 +1,61 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class MajorityElementTest {
+
+ @Test
+ void testGetMajorityElement0() {
+ int[] a = { 1, 1 };
+ assertEquals(1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+ }
+
+ @Test
+ void testGetMajorityElement1() {
+ int[] a = { 1, 2 };
+ assertEquals(-1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+ }
+
+ @Test
+ void testGetMajorityElement2() {
+ int[] a = { 1, 2, 1 };
+ assertEquals(1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+ }
+
+ @Test
+ void testGetMajorityElement3() {
+ int[] a = { 1, 2, 2 };
+ assertEquals(2, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+ }
+
+ @Test
+ void testGetMajorityElement4() {
+ int[] a = { 1 };
+ assertEquals(1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+ }
+
+ @Test
+ void testGetMajorityElement5() {
+ int[] a = { 1, 2, 2, 2 };
+ assertEquals(2, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+ }
+
+ @Test
+ void testGetMajorityElement() {
+ int[] a = { 2, 3, 9, 2, 2 };
+ assertEquals(2, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+ }
+
+ @Test
+ void testGetMajorityElement6() {
+ int[] a = { 1, 2, 3, 4 };
+ assertEquals(-1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+ }
+
+ @Test
+ void testGetMajorityElement7() {
+ int[] a = { 1, 2, 3, 1 };
+ assertEquals(-1, MajorityElement.getMajorityElement(a, 0, a.length - 1));
+ }
+
+}