@Ashutosh
I think a single pass would mean that you look at the element only once. But
in your algorithm you are looking at some elements multiple times using the
tail pointer. Does it then qualify the requirements ? Moreover, you are
indeed using extra memory.
On Sun, Aug 22, 2010 at 6:46 PM,
@Aravind: The intent was to do it in in one pass without extra memory,
and leave the input unchanged if the number of zeros does not equal
the number of ones. It seems to me that the combination of
requirements is tough.
Dave
On Aug 21, 10:22 pm, Aravind Prasad wrote:
> if the intention of the p
if the intention of the problem is to do it in O(n)..
then we can do 2 passses.. one to find the no of 0 and 1..
then in 2nd pass,, put 0 in even and 1 in odd and leave the rest of
the array as such..
O(n)+O(n)=O(n).
On Aug 20, 5:40 pm, Ashutosh Tamhankar wrote:
> Here is a C++ version of the
Here is a C++ version of the algorithm to solve this problem.
#include
#define TRUE 1
#define FALSE 0
typedef struct Binarr{
int iNumber;
};
class binaryarr{
Binarr * arr;
public:
int iHead;
int iSize;
int iZeroes;
int iOnes;
int iTail;
binaryarr(void);
~bi
@Rais: I don't see that it leaves the array unchanged if the number of
zeros does not equal the number of ones.
Dave
On Aug 19, 7:23 am, Rais Khan wrote:
> void ArrayShifting(int *str, int size)
> {
> int odd=1, even=0;
> while(odd < size)
> {
> int position;
> if(str
Dave, check my pseudo code. Both the tasks of checking if the number of 1s
and 0s is equal and sorting the array seems to to work in a single pass.
2010/8/19 Dave
> It seems easy enough to put all of the zeros in the even positions and
> all of the ones in the odd positions in one pass. The dif
It seems easy enough to put all of the zeros in the even positions and
all of the ones in the odd positions in one pass. The difficulty is
posed by the second condition, that if the number of zeros and ones is
not equal, then leave everything alone. This seems to require two
passes, either to deter
