CareerCup

As you scan the Array Generate a Max heap as you see an Even number and Create a Min Heap for Odd number. Once all the elements in the array are scanned. Perform heap sorts on both heaps.

just overwrite the < operator and do quicksort.

Will the soln given by bastard TV work? How?

Here is my implementation suggested by TV. Any comments are welcome!

void swap(int& x, int& y)
{
int t;

t = x;
x = y;
y = t;
}

int Partition(int a[], int l, int r)
{
int v = a[r];
int i = l-1;
int j = r;

while(j>i)
{
while(true)
{
++i;
if(a[i]%2==1 && v%2==1)
{
if(a[i] <= v)
break;
}
else if(a[i]%2==1 && v%2==0)
{
continue;
}
else if(a[i]%2==0 && v%2==1)
{
break;
}
else
{
if(a[i]>=v)
break;
}
}

while(true)
{
--j;
if(a[j]%2==1 && v%2==1)
{
if(a[j]>=v)
break;
}
else if(a[j]%2==1 && v%2==0)
{
break;
}
else if(a[j]%2==0 && v%2==1)
{
continue;
}
else
{
if(a[j]<=v)
break;
}
}

if(i>j)
break;

swap(a[i], a[j]);
}


swap(a[i], a[r]);
return i;
}

void mySort(int a[], int l, int r)
{
if(l>=r)
return;

int m = Partition(a, l, r);

mySort(a, l, m-1);
mySort(a, m+1, r);
}

shift all odd elements to left and even elements to right and form a min heap for even and max heap for odd elements..

best method is to multiply odd elements by a negative sign and then sort complete array afterwards remove negative sign

1: Multiply the odd elements by -1
2. Sort the numbers
3. Again multiply the odd numbers by -1.

I have one basic solution ,Yes It may have some space complexity

1)Do the Sorting for an array(Ascending Order)
2)As We know Odd Number should be in Increasing Order So Start to read the sorted from the end Till 0 subscript and read the same array from the starting for even number till a[n]
3) Store Evan and Odd Numbers in the separate arrays

So We can get easy solution for this prob Not Much Complexity Analysis.
Am i right ?

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int n;
scanf("%d",&n);
int ar[n];
for (int i=0; i<n; i++) {
scanf("%d",&ar[i]);
if (ar[i] % 2) {
ar[i] *= -1;
}
}
sort(ar, ar+n);
for (int i=0; i<n; i++) {
if (ar[i] % 2) {
ar[i] *= -1;
}
printf("%d ",ar[i]);
}
printf("\n");
return 0;
}