@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 <raja....@gmail.com> wrote:
> 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 <asshuto...@gmail.com> wrote:
>
>
>
> > Here is a C++ version of the algorithm to solve this problem.
>
> > #include <iostream>
> > #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);
> > ~binaryarr(void);
> > bool Rearrange(void);
> > bool IsOdd(int iNumber);
> > bool IsZero(int iNumber);
> > bool SwapElements(int iUnexpected, int iCurrTail, int iExpected);
> > bool ZeroOneBalanced(void);
> > void Display(void);
>
> > };
>
> > void binaryarr:: Display(void){
> > std::cout << std::endl << "Contents of the arr are";
> > for(int j=0; j<iSize;j++)
> > std::cout << std::endl<< arr[j].iNumber;
>
> > }
>
> > bool binaryarr:: ZeroOneBalanced(void){
> > int iTotal = -1;
> > iTotal = iOnes + iZeroes;
> > if (iTotal == iSize && iOnes != iZeroes){
> > std::cout << std::endl<<"Number of Ones =
> > "<<iOnes<<std::endl<<"Number of Zeros = "<<iZeroes;
> > return FALSE; // done or error occurred.
> > }
> > return TRUE;
>
> > }
>
> > // Builds the arr
> > binaryarr::binaryarr(void){
> > int iIndex = 0;
>
> > std::cout << "Enter the size of the arr\n";
> > std::cin >> iSize;
>
> > if(iSize != 0){
> > if ((iSize % 2) == 0)
> > {
> > std::cout << std::endl<<"Enter each zero or one and press
> > enter"<<std::endl;
> > arr = (Binarr *) malloc(iSize-1);
> > for (iIndex = 0 ; iIndex < iSize ; iIndex ++ )
> > std::cin >> arr[iIndex].iNumber;
> > iHead = 0;
> > iTail = iSize-1;
> > iZeroes = 0;
> > iOnes = 0;
> > }
> > else
> > {
> > std::cout << "The size of the arr cant fit equal number of zeros
> > and ones\n";
> > iHead = -1;
> > }
> > }
> > else
> > {
> > std::cout << "The size of the arr cant fit equal number of zeros
> > and ones\n";
> > iHead = -1;
> > }
>
> > }
>
> > // Free the memory
> > binaryarr::~binaryarr(void){
> > /*if (iHead != -1)
> > free(arr);*/
>
> > }
>
> > // is the given number odd or even
> > bool binaryarr::IsOdd(int iNumber){
> > if ( (iNumber == 0 ) )
> > return TRUE;
> > else
> > if (( (iNumber % 2) == 0 ) && (iNumber!=1) )
> > return TRUE;
> > else
> > return FALSE;
>
> > }
>
> > // is the given number zero or one
> > bool binaryarr::IsZero(int iNumber){
>
> > if (arr[iNumber].iNumber == 0){
> > iZeroes = iZeroes + 1;
> > return TRUE;
> > }
> > else
> > {
> > iOnes = iOnes + 1;
> > return FALSE;
> > }
>
> > }
>
> > bool binaryarr:: SwapElements(int iUnexpected, int iCurrTail, int
> > iExpected){
> > int iTemp = -1;
> > int iFound = -1;
> > /*while !((IsZero(iUnexpected)) && iExpected){
> > iCurrTail = iCurrTail - 1;
> > iFound = 1;
> > }*/
> > for (int iDecr = iCurrTail; iDecr >= iUnexpected; iDecr--)
> > {
> > if((IsZero(iDecr)) && (iExpected == 0) || (!(IsZero(iDecr))) &&
> > (iExpected == 1))
> > {
> > iFound = 1;
> > iTail = iDecr; // Reposition current tail.
> > iTemp = arr[iUnexpected].iNumber;
> > arr[iUnexpected].iNumber = arr[iDecr].iNumber;
> > arr[iDecr].iNumber = iTemp;
> > return TRUE;
> > }
> > }
> > //
>
> > if ((iFound == -1) || (iOnes != iZeroes))
> > {
> > std::cout << std::endl << "binaryarr:: SwapElements: Mismatch or
> > mismatch in num of zeros : ones. Expected = "<<iExpected<<".Unexpected =
> > "<<arr[iUnexpected].iNumber;
> > return FALSE;
> > }
>
> > }
>
> > // sort the input arr such that every odd position has a 1 and even position
> > a zero.
> > bool binaryarr::Rearrange(void){
>
> > for (iHead = 0; iHead < iTail; iHead++) {
> > if (IsOdd(iHead)) // Determine if the position on the arr is ODD
> > {
> > if (IsZero(iHead)) // Position is odd; but a zero encountered
> > {
> > /*if (iTail == iHead)
> > iTail = iTail +1;*/
> > // Expected is 1.
> > if (!(SwapElements(iHead,iTail, 1))) {
> > std::cout << std::endl <<"No matching element found for
> > element @:"<<iHead;
> > return FALSE;
> > }
> > else
> > std::cout << std::endl <<"Successfully swapped between
> > "<<iHead<<" & "<<iTail;
> > }
> > // arr head is 1
> > }
> > else // position is even
> > {
> > if (!(IsZero(iHead)))
> > {
> > if (!(SwapElements(iHead,iTail, 0))) {
> > std::cout << std::endl <<"No matching element found for
> > element @:"<<iHead;
> > return FALSE;
> > }
> > else
> > std::cout << std::endl <<"Successfully swapped between
> > "<<iHead<<" & "<<iTail;
> > }
> > // arr head is 0
> > }
>
> > }
> > Display();
> > if (!(ZeroOneBalanced()))
> > return FALSE;
> > return TRUE;
>
> > }
>
> > int main (int argc, char * const argv[]) {
> > binaryarr test;
> > if (test.iHead == -1)
> > std::cout << std::endl<<"Error:Number of zeros and ones cannot be
> > equal with this size of arr";
> > else
> > {
> > if (!(test.Rearrange()))
> > std::cout << std::endl << "Rearrange failed";
> > }
> > return 0;
>
> > }- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
