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