finding majority element in an array

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:

I/P : 3 3 4 2 4 4 2 4 4

O/P : 4

I/P : 3 3 4 2 4 4 2 4

O/P : NONE

A simple solution would be running 2 loops and check for all elements and store count of all elements… Time complexity will be  O(n^2).

Can you think of a better solution …

here I’m giving You a better solution .. Time complexity –  O(n)

Using Moore’s Voting Algorithm)

This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a)If a[maj_index] == a[i]
        count++
    (b)Else
        count--;
    (c)If count == 0
        maj_index = i;
        count = 1
3.  Return a[maj_index]

Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1.
First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element. Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.

<br />#include <bits/stdc++.h>
using namespace std;
int find_priority(int arr[], int n){
int c = 1,index = 0;
for(int i = 1; i < n; i++){
if(arr[index] == arr[i]){
c++;
}
else{
c--;
}
if(c == 0){
index = i;
c = 1;
}
}
return arr[index];
}

int main(){
int n;
cout<<"enter value of n"<<endl;
cin>>n;
int arr[n];
cout<<"enter array"<<endl;
for(int i = 0; i < n; i++){
cin>>arr[i];
}
int pr_ele = find_priority(arr,n);
int c = 0;
for(int i = 0; i < n; i++){
if(arr[i] == pr_ele)
c++;
}
if(c > n/2){
cout<<"majority element found"<<endl<<"element is "<<pr_ele<<endl<<"count is "<<c;
}
else cout<<"no majority element present";

}

Output :-

Majority Element in an Array

Maximum Submatrix Sum

This is a dynamic programming problem based on sliding window type of thing.In this problem We have to find the k*k size submatrix whoose sum is maximum.

here is the solution of the problem.

<br />#include<bits/stdc++.h>
using namespace std;

int main(){
int m,n,k;
cout<<"enter value of m , n, k"<<endl; cin>>m>>n>>k;
cout<<"enter matrix"<<endl;
int matrix[m][n];
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++) cin>>matrix[i][j];
int sum = 0;
int sum_matrix[m][n-k+1];
for(int i = 0 ; i < m; i++){
sum = 0;
for(int j = 0; j < k; j++)
sum = sum + matrix[i][j];
sum_matrix[i][0] = sum;
//            cout<<sum<<" ";
}
// cout<<endl<<endl;;

for(int i = 0; i < m; i++){
for(int j = 1 ; j < n-k+1; j++){
sum_matrix[i][j] = sum_matrix[i][j-1] + matrix[i][j+k-1]- matrix[i][j-1];
//        cout<<sum_matrix[i][j]<<" ";
}
//      cout<<endl;
}
//cout<<endl;
int maxs = INT_MIN;
int ksum_matrix[m-k+1][n-k+1];
int ksum = 0;
for(int j = 0 ; j < n-k+1; j++){
ksum = 0;
for(int i = 0; i < k; i++) ksum = ksum + sum_matrix[i][j]; if(ksum > maxs)
maxs = ksum;
ksum_matrix[0][j] = ksum;
//              cout<<ksum<<" ";

}
//   cout<<endl<<endl;

int maxm = maxs;
for(int j = 0; j < n-k+1; j++){
for(int i = 1 ; i < m-k+1; i++){
ksum_matrix[i][j] = ksum_matrix[i-1][j] + sum_matrix[i+k-1][j]- sum_matrix[i-1][j];
//          cout<<ksum_matrix[i][j]<<" ";
if(maxm < ksum_matrix[i][j])
maxm = ksum_matrix[i][j];
}
//        cout<<endl;
}
cout<<"max sum = "<<maxm;

}

Output :-

Maximum Sub-Matrix Sum

Why Quick Sort Is Better Than Merge Sort???

There are  Many reasons and I have listed some of them below…

1. Even though Quicksort has O(n^2) in worst case, it can be easily avoided with high probability by choosing the right pivot. By choosing random pivot variable We can get O(nlogn) behaviour   in 99% cases..

2. If Quick sort is implemented well, it will be around 2-3 times faster than merge sort and heap sort. This is mainly because that the operations in the innermost loop  are simpler.

3.Quick sort is in-place sorting algorithm where as merge sort is not in-place. In-place sorting means, it does not use additional storage space to perform sorting. In merge sort, to merge the sorted arrays it requires a temporary array and hence it is not in-place.

1. Its cache performance is higher than other sorting algorithms. This is because of its in-place characteristic.

2. The biggest advantage is locality of reference. Quicksort accesses continuos elements and thus is better in virtual memory elements as compared to mergesort which accesses distant elements in the merge routine.

Design A stack to get minimum in o(1) time.

Question: Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc.

Example:

Consider the following SpecialStack
16 –> TOP
15
29
19
18

When getMin() is called it should return 15, which is the minimum
element in the current stack.

If we do pop two times on stack, the stack becomes
29 –> TOP
19
18

When getMin() is called, it should return 18 which is the minimum
in the current stack.

Solution :=

Sieve of Eratosthenes – prime number generator

Description:-

A prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, … ; the p itself should not be marked ).
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

Code Implementation :-

<br />#include<iostream>
#include <cstring>
#include <ctime>
#include <cstdio>
using namespace std;

int markprime(bool arr[], int n, int i) {
int x = 2, p;
while((p = (i * x)) < n) {
arr[p] = true;
++x;
}

x = i+1;

while (arr[x]) x++;
return x;
}

int main(){
int n, i;
i = 2;
cout<<"enter the number to which you want to generate the prime numbers-like 100 for 0 - 100"<<endl;
cin >> n;

bool arr[n];
for(int i = 0; i < n; i++) arr[i] = false;

arr[0] = true;
arr[1] = true;

while ((i*i) <= n) {
i = markprime(arr,n,i);

}

for(i = 1; i < n; i++){
if(arr[i] == false)
printf("%d ", i);
}

return 0;
}

Output :-