Majority Element done!

Oh yeah, I had so much fun with this one! It really worked my brain and
gave me better appreciation of Divide and Conquer and Merge Sort! Philip
Guo's PythonTutor site is amazing! It really helped me in debugging my
recursive function. Fun fun fun!

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));
+	}
+
+}