Skip to main content

Find the majority element using bit logic

Here given code implementation process.

// C Program for
// Find the majority element using bit logic
#include <stdio.h>

void findMajorityElement(int arr[], int n)
{
	// Auxiliary variable
	int bits = 32;
	int count = 0;
	int x = 0;
	// This loop are work on range (1...31) bit number
	for (int i = 0; i < bits; ++i)
	{
		// Count active bits in ith position in every array element
		for (int j = 0; j < n; ++j)
		{
			if ((arr[j] & (1 << i)) != 0)
			{
				count++;
			}
		}
		if (count > (n / 2))
		{
			// Add value of i-th bit
			x += (1 << i);
		}
		count = 0;
	}
	// Count frequency of x element
	for (int i = 0; i < n; ++i)
	{
		if (arr[i] == x)
		{
			count++;
		}
	}
	if (count > n / 2)
	{
		// x appears more than n/2 times in the given array
		printf("\n Majority element is %d", x);
	}
	else
	{
		printf("\n No Majority element in this array ");
	}
}
int main()
{
	int arr[] = {
		1 , 7 , 3 , 7 , 4 , 3 , 7 , 7 , 51 , 7 , 7
	};
	// Get the length of array
	int n = sizeof(arr) / sizeof(arr[0]);
	// Test
	findMajorityElement(arr, n);
	return 0;
}

Output

 Majority element is 7
// Java program for
// Find the majority element using bit logic
public class Searching
{
	public void findMajorityElement(int[] arr, int n)
	{
		// Auxiliary variable
		int bits = 32;
		int count = 0;
		int x = 0;
		// This loop are work on range (1...31) bit number
		for (int i = 0; i < bits; ++i)
		{
			// Count active bits in ith position in every array element
			for (int j = 0; j < n; ++j)
			{
				if ((arr[j] & (1 << i)) != 0)
				{
					count++;
				}
			}
			if (count > (n / 2))
			{
				// Add value of i-th bit
				x += (1 << i);
			}
			count = 0;
		}
		// Count frequency of x element
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] == x)
			{
				count++;
			}
		}
		if (count > n / 2)
		{
			// x appears more than n/2 times in the given array
			System.out.print("\n Majority element is " + x);
		}
		else
		{
			System.out.print("\n No Majority element in this array ");
		}
	}
	public static void main(String[] args)
	{
		Searching task = new Searching();
		int[] arr = {
			1 , 7 , 3 , 7 , 4 , 3 , 7 , 7 , 51 , 7 , 7
		};
		// Get the length of array
		int n = arr.length;
		// Test
		task.findMajorityElement(arr, n);
	}
}

Output

 Majority element is 7
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Find the majority element using bit logic
class Searching
{
	public: void findMajorityElement(int arr[], int n)
	{
		// Auxiliary variable
		int bits = 32;
		int count = 0;
		int x = 0;
		// This loop are work on range (1...31) bit number
		for (int i = 0; i < bits; ++i)
		{
			// Count active bits in ith position in every array element
			for (int j = 0; j < n; ++j)
			{
				if ((arr[j] &(1 << i)) != 0)
				{
					count++;
				}
			}
			if (count > (n / 2))
			{
				// Add value of i-th bit
				x += (1 << i);
			}
			count = 0;
		}
		// Count frequency of x element
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] == x)
			{
				count++;
			}
		}
		if (count > n / 2)
		{
			// x appears more than n/2 times in the given array
			cout << "\n Majority element is " << x;
		}
		else
		{
			cout << "\n No Majority element in this array ";
		}
	}
};
int main()
{
	Searching *task = new Searching();
	int arr[] = {
		1 , 7 , 3 , 7 , 4 , 3 , 7 , 7 , 51 , 7 , 7
	};
	// Get the length of array
	int n = sizeof(arr) / sizeof(arr[0]);
	// Test
	task->findMajorityElement(arr, n);
	return 0;
}

Output

 Majority element is 7
// Include namespace system
using System;
// Csharp program for
// Find the majority element using bit logic
public class Searching
{
	public void findMajorityElement(int[] arr, int n)
	{
		// Auxiliary variable
		int bits = 32;
		int count = 0;
		int x = 0;
		// This loop are work on range (1...31) bit number
		for (int i = 0; i < bits; ++i)
		{
			// Count active bits in ith position in every array element
			for (int j = 0; j < n; ++j)
			{
				if ((arr[j] & (1 << i)) != 0)
				{
					count++;
				}
			}
			if (count > (n / 2))
			{
				// Add value of i-th bit
				x += (1 << i);
			}
			count = 0;
		}
		// Count frequency of x element
		for (int i = 0; i < n; ++i)
		{
			if (arr[i] == x)
			{
				count++;
			}
		}
		if (count > n / 2)
		{
			// x appears more than n/2 times in the given array
			Console.Write("\n Majority element is " + x);
		}
		else
		{
			Console.Write("\n No Majority element in this array ");
		}
	}
	public static void Main(String[] args)
	{
		Searching task = new Searching();
		int[] arr = {
			1 , 7 , 3 , 7 , 4 , 3 , 7 , 7 , 51 , 7 , 7
		};
		// Get the length of array
		int n = arr.Length;
		// Test
		task.findMajorityElement(arr, n);
	}
}

Output

 Majority element is 7
package main
import "fmt"
// Go program for
// Find the majority element using bit logic
type Searching struct {}
func getSearching() * Searching {
	var me *Searching = &Searching {}
	return me
}
func(this Searching) findMajorityElement(arr[] int, n int) {
	// Auxiliary variable
	var bits int = 32
	var count int = 0
	var x int = 0
	// This loop are work on range (1...31) bit number
	for i := 0 ; i < bits ; i++ {
		// Count active bits in ith position in every array element
		for j := 0 ; j < n ; j++ {
			if (arr[j] & (1 << i)) != 0 {
				count++
			}
		}
		if count > (n / 2) {
			// Add value of i-th bit
			x += (1 << i)
		}
		count = 0
	}
	// Count frequency of x element
	for i := 0 ; i < n ; i++ {
		if arr[i] == x {
			count++
		}
	}
	if count > n / 2 {
		// x appears more than n/2 times in the given array
		fmt.Print("\n Majority element is ", x)
	} else {
		fmt.Print("\n No Majority element in this array ")
	}
}
func main() {
	var task * Searching = getSearching()
	var arr = [] int {1 , 7 , 3 , 7 , 4 , 3 , 7 , 7 , 51 , 7 , 7}
	// Get the length of array
	var n int = len(arr)
	// Test
	task.findMajorityElement(arr, n)
}

Output

 Majority element is 7
<?php
// Php program for
// Find the majority element using bit logic
class Searching
{
	public	function findMajorityElement($arr, $n)
	{
		// Auxiliary variable
		$bits = 32;
		$count = 0;
		$x = 0;
		// This loop are work on range (1...31) bit number
		for ($i = 0; $i < $bits; ++$i)
		{
			// Count active bits in ith position in every array element
			for ($j = 0; $j < $n; ++$j)
			{
				if (($arr[$j] & (1 << $i)) != 0)
				{
					$count++;
				}
			}
			if ($count > ((int)($n / 2)))
			{
				// Add value of i-th bit
				$x += (1 << $i);
			}
			$count = 0;
		}
		// Count frequency of x element
		for ($i = 0; $i < $n; ++$i)
		{
			if ($arr[$i] == $x)
			{
				$count++;
			}
		}
		if ($count > (int)($n / 2))
		{
			// x appears more than n/2 times in the given array
			echo("\n Majority element is ".$x);
		}
		else
		{
			echo("\n No Majority element in this array ");
		}
	}
}

function main()
{
	$task = new Searching();
	$arr = array(1, 7, 3, 7, 4, 3, 7, 7, 51, 7, 7);
	// Get the length of array
	$n = count($arr);
	// Test
	$task->findMajorityElement($arr, $n);
}
main();

Output

 Majority element is 7
// Node JS program for
// Find the majority element using bit logic
class Searching
{
	findMajorityElement(arr, n)
	{
		// Auxiliary variable
		var bits = 32;
		var count = 0;
		var x = 0;
		// This loop are work on range (1...31) bit number
		for (var i = 0; i < bits; ++i)
		{
			// Count active bits in ith position in every array element
			for (var j = 0; j < n; ++j)
			{
				if ((arr[j] & (1 << i)) != 0)
				{
					count++;
				}
			}
			if (count > (parseInt(n / 2)))
			{
				// Add value of i-th bit
				x += (1 << i);
			}
			count = 0;
		}
		// Count frequency of x element
		for (var i = 0; i < n; ++i)
		{
			if (arr[i] == x)
			{
				count++;
			}
		}
		if (count > parseInt(n / 2))
		{
			// x appears more than n/2 times in the given array
			process.stdout.write("\n Majority element is " + x);
		}
		else
		{
			process.stdout.write("\n No Majority element in this array ");
		}
	}
}

function main()
{
	var task = new Searching();
	var arr = [1, 7, 3, 7, 4, 3, 7, 7, 51, 7, 7];
	// Get the length of array
	var n = arr.length;
	// Test
	task.findMajorityElement(arr, n);
}
main();

Output

 Majority element is 7
#  Python 3 program for
#  Find the majority element using bit logic
class Searching :
	def findMajorityElement(self, arr, n) :
		#  Auxiliary variable
		bits = 32
		count = 0
		x = 0
		i = 0
		#  This loop are work on range (1...31) bit number
		while (i < bits) :
			j = 0
			#  Count active bits in ith position in every list element
			while (j < n) :
				if ((arr[j] & (1 << i)) != 0) :
					count += 1
				
				j += 1
			
			if (count > (int(n / 2))) :
				#  Add value of i-th bit
				x += (1 << i)
			
			count = 0
			i += 1
		
		i = 0
		#  Count frequency of x element
		while (i < n) :
			if (arr[i] == x) :
				count += 1
			
			i += 1
		
		if (count > int(n / 2)) :
			#  x appears more than n/2 times in the given list
			print("\n Majority element is ", x, end = "")
		else :
			print("\n No Majority element in this array ", end = "")
		
	

def main() :
	task = Searching()
	arr = [1, 7, 3, 7, 4, 3, 7, 7, 51, 7, 7]
	#  Get the length of list
	n = len(arr)
	#  Test
	task.findMajorityElement(arr, n)

if __name__ == "__main__": main()

Output

 Majority element is  7
#  Ruby program for
#  Find the majority element using bit logic
class Searching 
	def findMajorityElement(arr, n) 
		#  Auxiliary variable
		bits = 32
		count = 0
		x = 0
		i = 0
		#  This loop are work on range (1...31) bit number
		while (i < bits) 
			j = 0
			#  Count active bits in ith position in every array element
			while (j < n) 
				if ((arr[j] & (1 << i)) != 0) 
					count += 1
				end

				j += 1
			end

			if (count > (n / 2)) 
				#  Add value of i-th bit
				x += (1 << i)
			end

			count = 0
			i += 1
		end

		i = 0
		#  Count frequency of x element
		while (i < n) 
			if (arr[i] == x) 
				count += 1
			end

			i += 1
		end

		if (count > n / 2) 
			#  x appears more than n/2 times in the given array
			print("\n Majority element is ", x)
		else
 
			print("\n No Majority element in this array ")
		end

	end

end

def main() 
	task = Searching.new()
	arr = [1, 7, 3, 7, 4, 3, 7, 7, 51, 7, 7]
	#  Get the length of array
	n = arr.length
	#  Test
	task.findMajorityElement(arr, n)
end

main()

Output

 Majority element is 7
// Scala program for
// Find the majority element using bit logic
class Searching()
{
	def findMajorityElement(arr: Array[Int], n: Int): Unit = {
		// Auxiliary variable
		var bits: Int = 32;
		var count: Int = 0;
		var x: Int = 0;
		var i: Int = 0;
		// This loop are work on range (1...31) bit number
		while (i < bits)
		{
			var j: Int = 0;
			// Count active bits in ith position in every array element
			while (j < n)
			{
				if ((arr(j) & (1 << i)) != 0)
				{
					count += 1;
				}
				j += 1;
			}
			if (count > (n / 2))
			{
				// Add value of i-th bit
				x += (1 << i);
			}
			count = 0;
			i += 1;
		}
		i = 0;
		// Count frequency of x element
		while (i < n)
		{
			if (arr(i) == x)
			{
				count += 1;
			}
			i += 1;
		}
		if (count > n / 2)
		{
			// x appears more than n/2 times in the given array
			print("\n Majority element is " + x);
		}
		else
		{
			print("\n No Majority element in this array ");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Searching = new Searching();
		var arr: Array[Int] = Array(1, 7, 3, 7, 4, 3, 7, 7, 51, 7, 7);
		// Get the length of array
		var n: Int = arr.length;
		// Test
		task.findMajorityElement(arr, n);
	}
}

Output

 Majority element is 7
import Foundation;
// Swift 4 program for
// Find the majority element using bit logic
class Searching
{
	func findMajorityElement(_ arr: [Int], _ n: Int)
	{
		// Auxiliary variable
		let bits: Int = 32;
		var count: Int = 0;
		var x: Int = 0;
		var i: Int = 0;
		// This loop are work on range (1...31) bit number
		while (i < bits)
		{
			var j: Int = 0;
			// Count active bits in ith position in every array element
			while (j < n)
			{
				if ((arr[j] & (1 << i))  != 0)
				{
					count += 1;
				}
				j += 1;
			}
			if (count > (n / 2))
			{
				// Add value of i-th bit
				x += (1 << i);
			}
			count = 0;
			i += 1;
		}
		i = 0;
		// Count frequency of x element
		while (i < n)
		{
			if (arr[i] == x)
			{
				count += 1;
			}
			i += 1;
		}
		if (count > n / 2)
		{
			// x appears more than n/2 times in the given array
			print("\n Majority element is ",
                  x, terminator: "");
		}
		else
		{
			print("\n No Majority element in this array ", 
                  terminator: "");
		}
	}
}
func main()
{
	let task: Searching = Searching();
	let arr: [Int] = [1, 7, 3, 7, 4, 3, 7, 7, 51, 7, 7];
	// Get the length of array
	let n: Int = arr.count;
	// Test
	task.findMajorityElement(arr, n);
}
main();

Output

 Majority element is  7
// Kotlin program for
// Find the majority element using bit logic
class Searching
{
	fun findMajorityElement(arr: Array < Int > , n: Int): Unit
	{
		// Auxiliary variable
		val bits: Int = 32;
		var count: Int = 0;
		var x: Int = 0;
		var i: Int = 0;
		// This loop are work on range (1...31) bit number
		while (i < bits)
		{
			var j: Int = 0;
			// Count active bits in ith position in every array element
			while (j < n)
			{
				if ((arr[j] and(1 shl i)) != 0)
				{
					count += 1;
				}
				j += 1;
			}
			if (count > (n / 2))
			{
				// Add value of i-th bit
				x += (1 shl i);
			}
			count = 0;
			i += 1;
		}
		i = 0;
		// Count frequency of x element
		while (i < n)
		{
			if (arr[i] == x)
			{
				count += 1;
			}
			i += 1;
		}
		if (count > n / 2)
		{
			// x appears more than n/2 times in the given array
			print("\n Majority element is " + x);
		}
		else
		{
			print("\n No Majority element in this array ");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Searching = Searching();
	val arr: Array < Int > = arrayOf(1, 7, 3, 7, 4, 3, 7, 7, 51, 7, 7);
	// Get the length of array
	val n: Int = arr.count();
	// Test
	task.findMajorityElement(arr, n);
}

Output

 Majority element is 7
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment