WAP to Genrate All Possible Subset of Set S..Thats The Power Set

Algorithm:

Powerset: A recursive algorithm

If S = (a, b, c) then the powerset(S) is the set of all subsets

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

The first "trick" is to try to define recursively.

What would be a stop state?
S = () has what powerset(S)?

How get to it?
Reduce set by one element

Consider taking an element out - in the above example, take out {c}

S = (a,b) then powerset(S) = {(), (a), (b), (a,b), }

What is missing?
powerset(S) = { (c), (a,c), (b,c), (a,b,c)}

hmmm
Notice any similarities? Look again...
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

take any element out

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} IS

powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with
{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}

powerset(S) = powerset(S - {e_i}) U ({e_i} U powerset(S - {e_i}))

where e_i is an element of S (a singleton)

Pseudo-algorithm

1. Is the set passed empty? Done
2. If not, take an element out
   • recursively call method on the remainder of the set
   • return the set composed of the Union of
     (1) the powerset of the set without the element (from the recursive call)
     (2) this same set (i.e., (1)) but with each element therein unioned with the element initially taken out

Go backwards:
powerset(S) when S = {()} is {()}
powerset(S) when S = {(a)} is {(), (a)}
powerset(S) when S = {(a,b)} is {(), (a), (b), (a,b)}
etc...


Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

If S has n elements in it then P(s) will have 2^n elements



1st using Recursion

public class PowerSet {


private void printPowerSet(String inputString, String prefixString, int startIndex){
if(inputString == null){
return;
}
for(int i=startIndex;iString str = "";
str = prefixString + inputString.charAt(i);
System.out.println("{" + str + "}\n");
printPowerSet(inputString, str, i+1);
}

}




public static void main(String args[]){
String inputStr ="123";
System.out.println("{ }\n");
for(int i=0; iPowerSet powerSet = new PowerSet();

System.out.println("{" + inputStr.charAt(i) + "}\n");
powerSet.printPowerSet(inputStr, Character.toString(inputStr.charAt(i)), i+1);

}
}


}

TC O(n^2)
Sc O(n)

Run here https://ideone.com/8RuF1


2nd Iterative Method

Algorithm:

Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline

Example:

Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111

Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc


#include
#include

void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;

/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1< printf("%c", set[j]);
}
printf("\n");
}
}

/*Driver program to test printPowerSet*/
int main()
{
char set[] = {'a','b','c','d'};
printPowerSet(set, 4);

getchar();
return 0;
}

TC O(n*2^n)
SC O(1)
Rune Here https://ideone.com/z5tHG


Java program for Doing The Same

class PowerSet {

int arr[]={1,2,3};
int number=0;
void powerSet(){
for(int i=0;iint k=i;
int counter=0;
while(k>0){
if((k & 1) == 1){
System.out.print(arr[counter]);

}
counter++;
k=k>>1;
}
System.out.println();
number++;
}

}
public static void main(String[] args) {
PowerSet p=new PowerSet();
p.powerSet();
System.out.println("Total number of subsets are"+p.number);

}

}

Run Here https://ideone.com/LtjsT


More  http://en.wikipedia.org/wiki/Power_set
http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch1/solutions/recursionSol.html
http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java
http://rosettacode.org/wiki/Power_set
http://ruslanspivak.com/2011/06/09/power-set-generation-a-joy-of-python/
http://www.roseindia.net/tutorial/java/core/powerset.html
http://shriphani.com/blog/2008/03/31/one-step-forward-two-steps-back/
http://planetmath.org/?op=getobj&from=objects&id=136

WAP to Genrate All Possible Subset of Set S..Thats The Power Set

Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

If S has n elements in it then P(s) will have 2^n elements


Algorithm:

Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline

Example:

Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111

Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc

WAP to Generate Unique Combination from Given Set ot String

What is combination and how is it different from a permutation?

The mathematics' gurus would know this by heart, but I am going to refer to the Wikipedia for a proper definition.

"A combination is an un-ordered collection of unique sizes. (An ordered collection is called a permutation.)" from the Wikipedia article.

For example,

For a given String "ABCD",
a combination of un-ordered collection of unique sizes will be
[ABCD, BCD, ABD, ABC, ACD, AC, AD, AB, BC, BD, CD, D, A, B, C]

From my quick Google search, I also found out

"Number of ways of selecting zero or more things from ‘n’ different things is given by:- ( 2 ^ n - 1 ) "(from this article).

If we apply this formula in the above example, String "ABCD" with length of 4 should have ( 2 * 2 * 2 * 2 ) - 1 = 15 combinations.

This is exaclty what we are going to acheive in our code - Finding all possible combinations of characters from a given String. Note that for simplicity, we are going to assume that the input String (whose different combinations are going to be found) would not have any repetitive characters in it.
What is recursive programming?

Lets get a formal definition from Wikipedia:

"Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at."

In very simple terms, a method calling itself again and again until a particular condition is met is called recursive programming.
Implementation:

The algorithm discussed below to solve this problem is chosen for its simplicity and ease of understanding. It may not be the most effective algorithm but it definitely solves this particular problem and is extremely simple.

Some points to note about this problem.

1. The given String itself is one of the combinations. For example, one of the combinations of the String "ABCD" is "ABCD" itself.

2. Every character in the String will be a combination. For example, for the String "ABCD" -- > "A", "B", "C", "D" will be some of the combinations.
Algorithm

To find the combinations of a String:

Step 1: Add the String to the combination results.
Step 2: If the String has just one character in it,
then stop the current line of execution.
Step 3: Create new sub-words from the String by removing one letter at a time.
If the String is "ABCD", form sub-words like "BCD", "ACD", "ABD", "ABC"
Step 4: For each of the sub-word, go to Step 1


import java.io.IOException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class StringCombinations
{
private Set combinations = new HashSet();

public StringCombinations(String sInputString)
{
generate(sInputString);
System.out.println("*** Generated " + combinations .size() + " combinations ***");
System.out.println(combinations);

}

public void generate(String word)
{
// Add this word to our combination results set
// System.out.println(word);
combinations.add(word);

// If the word has only one character we break the
// recursion
if (word.length() == 1)
{
combinations.add(word);
return;
}

// Go through every position of the word
for (int i = 0; i < word.length(); i++)
{
// Remove the character at the current position
// all call this method with that String (Recursion!)
generate(word.substring(0,i) + word.substring(i+1));
}
}

public static String readCommandLineInput(String inputMessage)
{

String inputLine ="abcd";
return inputLine;
}

public static void main(String args[])
{
// Request and read user input
String sInstruction = "Enter a String: \n";
String sInputString = readCommandLineInput(sInstruction);
new StringCombinations(sInputString);
}

}// End of StringCombinations

Run Here https://ideone.com/EPV9i

Another Informative Link http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117

There are n rocks in the river, using which the frog can leap across the river.

I saw a discussion on this question on careercup as its good question..so i pasted it here

A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4

Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths. Ofcourse there can be other arguments too.



A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4

Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths.


#include
#include
#include


void printFrogLeap (int* pArray, int num, int count)
{
if(count > num)
{
return;
}
if(count == num)
{
int i;
if(pArray[count-1] == 1) /*path is complete or not*/
{
for (i=0; i < num; i++)
{
if (pArray[i] == 1)
{
printf ("[%d]", i+1);
}
}
printf ("\n");
}
return;
}
pArray [count] = 1;
printFrogLeap (pArray, num, count+1);
if(count+1 < num)
{
pArray [count+1] = 0;/*exclude this entry from path, since its used*/
}
printFrogLeap (pArray, num, count+2);
if(count+2 < num)
{
pArray [count+2] = 0;/*exclude this entry from path, since its used*/
}
}



int main ()
{
int *array, num=4;

array = (int*)malloc (sizeof(int)*num);
memset (array,0x00,num);
printf ("Total paths: \n");
printFrogLeap (array, num, 0);
free (array);
return 0;
}

Run Here https://ideone.com/o00za
Solution By Tully From CareerCup

You have a string "RGBBGBGR". Eliminate the pairs (two same chars adjacent to each other) recursively.

Example:
RGBBGBGR --> RGGBGR-->RBGR
Answer: Here recursively mean not a recursive function but to do it in the manner shown in example. Still we can do it recursively like below:

Fun_rcur(string)
{
if pairs
Remove pairs in string
Fun_recur(string)
Else
Return
}

But this is very costly:
1) Extra space (stack space for recursive calls)
2) You need to go through entire string in each recursive call.

Lets see an iterative approach for the same. We should check if we have character pair then cancel it and then check for next character and previous element. Keep canceling the characters until you either reach start of the array, end of the array or not find a pair.



C Code Complexity O(N^2) & Space O(1) Recursion

#include
#include
void couple_remove(char []);
int main(){
char arr[]="RGBBGBGR";// "RGBBGBGRRGRR";
couple_remove(arr);
printf("\n\n%s\n\n", arr);
return 0;
}

void couple_remove(char arr[]){
int remove=0,i,j;
int len=strlen(arr);
for(i=0;i if( arr[i]== arr[i+1] ){
for(j=i+2;j<=len;j++) {
arr[i]=arr[j];
i++;
remove=1;
}
}
if ( remove )
break;
}
if ( remove )
couple_remove(arr);
}

Rune Here https://ideone.com/urZEo


Java Code Complexity O(n) & Space O(n) Iterative

import java.util.Stack;
class CoupleElimination {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Stack st = new Stack();
String inputString = "RGBBGBGR";
for( int i=0 ; i < inputString.length() ; i++ )
{
char ch = inputString.charAt(i);
char top ;
if( !st.empty())
{
top = st.peek();

if( top == ch)
st.pop();
else
st.push(ch);
}

else
st.push(ch);
}
String result = "";
while( !st.empty() )
{
result = st.pop()+result;
}
System.out.println(result);
}
}

Run Here https://ideone.com/UF0Ao

WAP to Given a doubly linked list with just 3 numbers 0,1,2 . Sort it

Only Important Part is This Its Tricky to Solve
Traverse list and count '0', '1' and '2'. (O(N))

int zerosCount = 10;
int onesCount = 5;
int twosCount = 4;

Traverse list and fill according to counters. (O(N))

Time: O(N)
Space: O(1)


/* Program to reverse a doubly linked list */
#include
#include

/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};


struct node* sort(struct node *head)
{
struct node* current=head;
struct node* temp=NULL;
if (current!= NULL)
{
int zeroCount = 0;
int oneCount = 0;
int twoCount = 0;

//Find out the count for 0, 1 and 2
while(current!=NULL)
{
if (current->data == 0) {
zeroCount++;
} else if (current->data == 1) {
oneCount++;
} else if (current->data == 2) {
twoCount++;
}
else
{
break;
}
current=current->next;
}

//Fill a based on counts of 0, 1 and 2

temp=head;
for (int i = 0; i < zeroCount; i++)
{
temp->data = 0;
temp=temp->next;

}
for (int i = 0; i < oneCount; i++) {
temp->data = 1;
temp=temp->next;
}
for (int i = 0; i < twoCount; i++) {
temp->data = 2;
temp=temp->next;
}
}
temp=head;
return temp;
}

/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 2);


sort(head);

printf("\n Original Linked list ");
printList(head);


getchar();
}
Not Efficient Because it Requires 3 Paas Over Array
TC O(n)
SC O(1)
Run Here https://ideone.com/XdipA


As You Can See Above method Will take More Instruction to Execute , because it requires same thing to be do in three pass can't we do in single pass . yeas there exist an algorithm Named 3-Way Partioning or Dutch National Flag Algorithm , so that we can finish it in single pass & can make program more efficient.

But Above Algo Requires Mid points to be calculated , Again & Again until Array or list is not empty ..so think getting the mid point in array can be done in O(1) & for n items we repeat the things & can be done in O(logn) because we know starting & ending of array but what to do in-case of linked list calculating the mid point will take O(logn) & for n item this algo will take O(nlogn) ..ohh we are beyond of limit ..we din't expected this Time for an O(n) Solution...but we can add some pointer overhead for maintaining start & end location of o,1,2 & then in finally we can append 1's to 2's & 2's to 3's isn't ..yes it will work & we have done

so Algorithms is

1 Divide the list into 3 different lists,
2 list0 having all 0's, list2 having all 1's and list2 having all 2's
3 Concatenate list0, list1 and list2


2nd Method Implementation

/* Program to reverse a doubly linked list */
#include
#include

/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};


struct node* sort(struct node *head)
{
struct node* current=head;
struct node* start0=NULL;
struct node* start1=NULL;
struct node* start2=NULL;
struct node* n0=NULL;
struct node* n1=NULL;
struct node* n2=NULL;

if(!current)
return NULL;


while(current)
{
switch(current->data)
{
case 0:
if(n0)
{
n0->next=current;
}
else
{
start0=current;
}
n0=current;
break;

case 1:
if(n1)
{
n1->next=current;
}
else
{
start1=current;
}
n1=current;
break;

case 2:
if(n2)
{
n2->next=current;
}
else
{
start2=current;
}
n2=current;
break;
}
current=current->next;
}



if(n0)
n0->next=start1;
if(n1)
n1->next=start2;
if(n2)
n2->next=NULL;

return start0;


}

/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 1);
push(&head, 0);
push(&head, 1);
push(&head, 2);


head=sort(head);

printf("\n Sorted Linked list ");
printList(head);


getchar();
}

Advantage Sorting Can Be Done in Single Pass
TC O(n)
SC O(1)
Run Here https://ideone.com/clone/Ny3OI


Feel Free to Comment if you Find Anything Wrong Above..??

WAP to Program The Combinations of Number That Sums Up to Given Traget Number..Print Unique Combinations Only

Given a target number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the target.

Here order is not important, so don’t print the duplicated combination.

e.g. target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3)


Solution:
To search for all combination, we use a backtracking algorithm. Here, we use the above example of candidate={2,3,6,7} and target=7.

First, we start with a sum of 0. Then, we iterate over all possibilities that can be added to sum, which yields the possible set of sum={2,3,6,7}. Assume now that sum=2, we continue adding all possible candidate numbers {2,3,6,7} to sum=2, which yields sum={4,5,8,9}. Each step we have to use an array to keep track of all the indices of candidate numbers that add to the current sum, so that we can print the combination later. The next case would be sum=3. We look at all possible candidate numbers {3,6,7} to be added to sum=3, which yields sum={6,9,10}. Note that there is no need to look backward (ie, candidate numbers that are smaller than 3), as this would only yield duplicate results. We keep doing this recursively, until we reach the conditions below, where we stop.

We stop when the sum is greater than the target sum. Why? Remember our earlier assumption that candidate numbers must all be positive? Since the candidate array contains only positive numbers, if we continue searching, we would only add larger numbers to the sum, and this would not help us achieving the target sum. The other case where we stop is when the sum is equal to the target sum. We have found a valid combination.


#include
using namespace std;

void printSum(int candidates[], int index[], int n) {
for (int i = 1; i <= n; i++)
cout << candidates[index[i]] << ((i == n) ? "" : "+");
cout << endl;
}

void solves(int target, int sum, int candidates[], int sz, int index[], int n) {
if (sum > target)
return;
if (sum == target)
printSum(candidates, index, n);

for (int i = index[n]; i < sz; i++) {
index[n+1] = i;
solves(target, sum + candidates[i], candidates, sz, index, n+1);
}
}

void solve(int target, int candidates[], int sz) {
int index[10000];
index[0] = 0;
solves(target, 0, candidates, sz, index, 0);
}

int main()
{
int a[]={2,3,6,7};
solve(7,a,4);

}

I Discussed It with My Friend Ashim kapoor & after that we are able to solve4 it without repeatation

2nd Method

#define MAX_POINT 4
#define ARR_SIZE 100
#include

/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);

/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int arr[ARR_SIZE],int n, int i)
{

/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
// static int arr[ARR_SIZE];

if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= MAX_POINT; k++)
{
arr[i]= k;
printCompositions(arr,n-k, i+1);
}
}
}

/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
int i,flag=1;

for (i = 0; i < arr_size; i++)
if(arr[i]>arr[i+1]) flag=0;
if(flag)
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}

/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 and 3 of %d are\n", n);
int arr[ARR_SIZE]={1,2,3,4};
printCompositions(arr,n, 0);
getchar();
return 0;
}

Run Here https://ideone.com/NCrkD


Java Code for doing the same.

class PrintAllCombi {



/**
* @param args
*/
public static void main(String[] args) {
int s = 6;
int[] a = new int[] {2,3,6,7,8};
getCombi(a, 0, s, 0, "");
}

private static void getCombi(int[] a, int j, int s, int currentSum, String st) {
if(s == currentSum) {
System.out.println(st);
return;
}
if(currentSum > s) {
return;
}
for(int i=j; igetCombi(a, i, s, currentSum+a[i], st+"+"+a[i]);
}
}


}

Run Here https://ideone.com/XiWAF

Dominator of an array ...Majority Element In Different Way

Majority Element Different Possible Solutions


Solution 1: A basic solution is to scan entire array for checking for every element in the array. If any element occurs more than n/2 time, prints it and break the loop. This will be of O(n^2) complexity.

Solution 2: Sort the entire array in O(nlogn) and then in one pass keep counting the elements. This will be of O(nlogn) + O() = O(nlogn) complexity. #try it

Solution 3 Using BitCount Array

#include
int findmaj(int arr[], int n)
{
int bitcount[32];
int i, j, x;

for(i = 0; i < 32; i++)
bitcount[i] = 0;
for (i = 0; i < n; i++)
for (j = 0; j < 32; j++)
if (arr[i] & (1 << j)) // if bit j is on
bitcount[j]++;
else
bitcount[j]--;

x = 0;
for (i = 0; i < 32; i++)
if (bitcount[i] > 0)
x = x | (1 << i);
return x;
}

int main()
{
int i;
int arr[5] = {1, 3 ,1, 1, 3};

printf(" %d ", findmaj(arr, 5));

getchar();
return 0;
}

We keep a count of frequency of each of the bits. Since majority element will dominate the frequency count, hence we can get its value.

The solution is constant space and linear time : O(n)

Method 4 (Using Binary Search Tree)

Node of the Binary Search Tree (used in this approach) will be as follows. ?
struct tree
{
int element;
int count;
}BST;

Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)

METHOD 5 (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.

Example:
A[] = 2, 2, 3, 5, 2, 2, 6
Initialize:
maj_index = 0, count = 1 –> candidate ‘2?
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 5 => maj_index = 3, count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 2 => maj_index = 4
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1

Finally candidate for majority element is 2.

First step uses Moore’s Voting Algorithm to get a candidate for majority element.

2. Check if the element obtained in step 1 is majority

printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print "NONE"

# include<stdio.h>
# define bool int

int findCandidate(int *, int);
bool isMajority(int *, int, int);

void printMajority(int a[], int size)
{
int cand = findCandidate(a, size);

if(isMajority(a, size, cand))
printf(" %d ", cand);
else
printf("NO Majority Element");
}

int findCandidate(int a[], int size)
{
int maj_index = 0, count = 1;
int i;
for(i = 1; i < size; i++)
{
if(a[maj_index] == a[i])
count++;
else
count--;
if(count == 0)
{
maj_index = i;
count = 1;
}
}
return a[maj_index];
}

bool isMajority(int a[], int size, int cand)
{
int i, count = 0;
for (i = 0; i < size; i++)
if(a[i] == cand)
count++;
if (count > size/2)
return 1;
else
return 0;
}

int main()
{
int a[] = {1, 3, 3, 1,1,1,2,3,1,2,1,1};
printMajority(a, 12);
getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space : O(1)
Run Here http://ideone.com/ALf5fY

Amplitude of Element In Unsorted Array

/*
The amplitude of a non-empty zero-indexed array A consisting of N numbers is defined as

amplitude(A) = max { A[P] - A[Q] : 0 <= P, Q < N }

Write a function

int amplitude(int[] A);

that given a non-empty zero-indexed array A consisting of N non-negative integers returns its amplitude. Assume that the length of the array does not exceed 1,000,000. Assume that each element of the array is a non-negative integer not exceeding 5,000,000.

For example, given array A such that

A[0]=10, A[1]=2, A[2]=44, A[3]=15, A[4]=39, A[5]=20

the function should return 42.

*/

Java Code

class array
{
public static void main(String a[])

{

System.out.println(amplitude(new int[]{10, 2, 44, 15, 39, 20}));

}

static int amplitude ( int[] A )
{
// write your code here
int min=A[0];
int max=A[0];
int diff=0;

if(A==null)
return 0;
if(A.length==0)
return 0;

if(A.length>1000000)
{
return 0;
}
else
{

for(int i=0;i {
if(A[i] min=A[i];
if(A[i]>max)
max=A[i];

diff=max-min;
}

}
return diff;
}

}

Ugly Number e.g. Numer Whose prime Factor are 2 or 3 or

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 150′th ugly number.

1st Method

using namespace std;
#define MAXSIZE 15
 
int minimum(int x,int y,int z)
{
    if (x      return (y}
 
int nextUgly(int nth)//nth
{
    int num2,num3,num5;
    int ugly[MAXSIZE], ptr2, ptr3, ptr5;
        ugly[0]=1;int i=0;
        ptr2=ptr3=ptr5=0;
 
   for(i=1;i  {
    num2=ugly[ptr2]*2;
    num3=ugly[ptr3]*3;
    num5=ugly[ptr5]*5;
 
    ugly[i]=minimum(num2,num3,num5);
 
    if(ugly[i]==num2) ptr2++;
    if(ugly[i]==num3) ptr3++;
    if(ugly[i]==num5) ptr5++;
 
   }
 
    return ugly[nth-1];
}
 
int main()
{
 
    printf("15th Ugly number is %d\n",nextUgly(15));
}


TC O(n)
SC O(1)

2nd Method

Loop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.

To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.

For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.


# include
# include

/*This function divides a by greatest divisible
power of b*/
int maxDivide(int a, int b)
{
while (a%b == 0)
a = a/b;
return a;
}

/* Function to check if a number is ugly or not */
int isUgly(int no)
{
no = maxDivide(no, 2);
no = maxDivide(no, 3);
no = maxDivide(no, 5);

return (no == 1)? 1 : 0;
}

/* Function to get the nth ugly number*/
int getNthUglyNo(int n)
{
int i = 1;
int count = 1; /* ugly number count */

/*Check for all integers untill ugly count
becomes n*/
while (n > count)
{
i++;
if (isUgly(i))
count++;
}
return i;
}

/* Driver program to test above functions */
int main()
{
unsigned no = getNthUglyNo(150);
printf("150th ugly no. is %d ", no);
getchar();
return 0;
}

TC O(n)
SC O(1)
Run Here https://ideone.com/zyBWV