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;
>
>
>
> }
--
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.
