Let's define a term "RANDOMNESS" of array as...
summation of position of each 1's
for eg
RANDOMNESS for
(0,0,1,0,1,0,1,1)
will be
23
now calculate max possible RANDOMNESS for the given array (each 1 on max
possible right position)
here it will be 26
so ans will be-->
MAX RANDOMNESS of given arra
*Using Stack : *
j = 0;
for ( int i = 0; i < prefix.len(); i++ ) {
if ( isOperator(prefix[i]) ) stk.push(prefix[i]);
else {
postfix[j] = prefix[i];
j++;
while ( !stk.empty() && stk.top == '#' ) {
I think this algo is correct.
On Sunday, 1 July 2012 13:06:17 UTC+5:30, Ashu wrote:
>
> count=0;
> Start parsing from left to right
> If operator push in stack.
> In number add in queue and increment count by one,
> if count == 2 then
> pop from stack add in queue, decrements the count by one.
>
count=0;
Start parsing from left to right
If operator push in stack.
In number add in queue and increment count by one,
if count == 2 then
pop from stack add in queue, decrements the count by one.
On Friday, 29 June 2012 19:46:43 UTC+5:30, zerocool142 wrote:
>
> Given an integer expression in a
minimum number of swaps required to sort the given input array = no. of
inveresions in the array
No. of inversions in the array is defined as no. of pairs (i,j) such that
a[i] > a[j] && ihttps://groups.google.com/d/msg/algogeeks/-/44gDXly-hq0J.
To post to this group, send email to algogeeks@
Hi,
This one is quite easy. You have to calculate the number of one's before
every zero and add them up. That's it.
public class Test1 {
public void printArray(int[] tmpArr) {
for (int i : tmpArr) {
System.out.println(i);
}
}
public int calculateMinSwaps(int[] tmpArr) {
int minSwaps = 0;
int n
get the right most zero and left most one if index of right most zero is
less than the index of left most one ,the problem is solved other wise swap
0 and 1 and so on...
i argue this will give minimum swaps...
--
You received this message because you are subscribed to the Google Groups
"Algor
@deepika anand
solution given by me is for getting number of swap's in O(n)
as far as sorting goes any O(n lgn) algo can be used .
if count sort is allowed then O(n) for sorting also.[constant extra space.. ]
On Sat, Jun 23, 2012 at 12:49 AM, ashish jain wrote:
> @all
>
> yaa.. For getting nu
@all
yaa.. For getting number of swaps.. we have to calculate total number of
zeroes on the right for each '1' and on adding them
we will get the number of swaps. and in O(n) time.
On Sat, Jun 23, 2012 at 1:16 PM, Guruprasad Sridharan <
sridharan.mi...@gmail.com> wrote:
> It will work because
It will work because we need to swap only adjacent elements. So we do a
sweep from left to right finding the number of ones encountered to the left
of a zero when we find a zero. We keep adding the number as we sweep the
entire length.
On Sat, Jun 23, 2012 at 1:14 PM, deepikaanand wrote:
> @saura
start scanning the array from last .. maintain two pointers. one for last
encountered zero. second for moving backward. whenever you encounter the
one just swap it with the last zero. enhance the pointer till next zero
encounters. at last you will have the number of swaps.
I think my solution
if we just need to determine number of swaps, it can be Done in O(n)
Ex : 11100010
start counting number of zeros from the end
so we have zeroCount = 1
whenever we encounter a 1 we add current zeroCount to numberOfSwaps
so numberOfSwaps = 1
and so on the final value of numberOsSwaps is the answe
@saurabh..wat array r u getting finallyis it all 1's or in sorted
order for the input
int a[8]={1,1,1,0,1,0,1,1};
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubsc
@ALL
see if this work's :
#include
using namespace std;
int a[8]={0,0,1,0,1,0,1,1};
int count_zero(int size)
{ int i,count =0;
for(i=0;i wrote:
> i think it can be done in O(n)
> for each 1, calculate no. of zeros in right
> and adding all no. of zeros in right of all 1's will give no. of
i think it can be done in O(n)
for each 1, calculate no. of zeros in right
and adding all no. of zeros in right of all 1's will give no. of swaps.
correct me if i am wrong
On Sat, Jun 23, 2012 at 12:19 PM, Sourabh Singh wrote:
> @deepika
>
> yes, it's giving number of swaps.
> still Linear time
@deepika
yes, it's giving number of swaps.
still Linear time solution would be better :-)
On Fri, Jun 22, 2012 at 11:38 PM, deepikaanand wrote:
>
> will bubble sort give number of swaps??
>
> I tried the (bubble sort) code of 1,0,0,1,1,0,1 >swapcount = 5
> and for the array (0,0,1,0,1,0,1,1
will bubble sort give number of swaps??
I tried the (bubble sort) code of 1,0,0,1,1,0,1 >swapcount = 5
and for the array (0,0,1,0,1,0,1,1)>swapcount = 3
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send em
17 matches
Mail list logo