8. Find Majority element

-

8. Find Majority element


Problem link :- click here


package program;

public class Searching__8
{

	/*
	 	Given an array of n elements. Find the majority element in the array.
	 	A majority element in an array of size n is an element that appears 
	 	more than n/2 times in the array.
	 			arr[] = {3, 1, 3, 3, 2}\
	 			output : 3
	 			
	 	We have solved a problem in arrays where we have to find the element 
	 	which has repeated more than n/k times 
	 	we solved that problem in steps as follows 
	 	step 1 :- we selected (k-1) elements which has repeated most 
	 	step 2 :- we returned the array of elements which repeated more 
	 			than n/k times among those selected (k-1) elements
	 			
	 	Here we have to find element which has repeated more than n/2 times 
	 		k = 2 		k - 1 = 1
	 	therefore we have to select only one element
	 	and check if that element is repeated n/2 times
	 */
	
	static int majorityElement(int arr[], int n)
	{
		int element = arr[0];
		int count = 0;
		//finding one element which has occurred most
		for(int i=0; i<n; i++)
		{
			if(count == 0)
			{
				element = arr[i];
				count++;
			}
			else if(arr[i] == element)
				count++;
			else
				count--;
		}
		
		//checking if that element has occurred more than n/2 times
		count = 0;
		for(int i=0; i<n; i++)
		{
			if(arr[i] == element)
				count++;
		}
		
		if(count > n/2)
			return element;
		else
			return -1;
	}
	
	
	public static void main(String[] args)
	{
		int arr[] = {3, 2, 2, 3, 2};
		int ans = majorityElement(arr, arr.length);
		System.out.println("Majority element is : " + ans);
	}

}

Time complexity :- O(n)
Space complexity :- O(1)

Comments

Post a Comment

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

-
Image
4.Sort an array of 0's, 1's & 2's. Problem link :- click here C code #include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void sort_012(int A[], int n) { int i, j, m; i = 0; j = n-1; m = 0; while(m<=j) { if(A[m] == 0) { swap(&A[i], &A[m]); i++; m++; } else if(A[m] == 1) { m++; } else { swap(&A[j], &A[m]); j--; } } } void main() { int arr[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array(only 0, 1, or 2)\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n...
Read more

1. Reverse

-
Image
1. Reverse the Array.   Problem link :- Reverse the array Algorithm idea :- C code //Reverse the array #include<stdio.h> void rev_arr(int arr[], int start, int end) { int temp; while(start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } void print_arr(int arr[], int size) { int i; for(i=0; i<size; i++) printf("\t%d",arr[i]); printf("\n"); } void main() { int arr1[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr1[i]); printf("Array before reversing\n"); print_arr(arr1, n); rev_arr(arr1, 0, n-1); printf("\nArray after reversing\n"); print_arr(arr1, n); } Java code //Reverse the array package programs;...
Read more

3. Height of Binary tree

-
3. Height of Binary tree Problem link :- click here package Binary_Tree; public class BinaryTree__3 { static int heightOfTree(Node root) { if(root == null) return 0; int left_height = heightOfTree(root.left); int right_height = heightOfTree(root.right); return Math.max(left_height, right_height) + 1; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int arr[] = {2, -1, 3, -1, -1, 3}; tree.root = tree.createTree(arr, 0); int ans = heightOfTree(tree.root); System.out.println("Height : " + ans); } } Time complexity :- O(n) Space complexity :- O(n)
Read more