Tuotuo
BAN USER
Comments (10)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Test the code below, it is O(n), memory usage O(1). Cheers!!!
#include <iostream>
using namespace std;
void sortoddeven(int * a, int n)
{
int oddcount = 0;
for(int i = 0; i<n; i++)
oddcount += a[i]%2;
int i_e = oddcount;
int i_o = 0;
int i = 0;
while(i_o<oddcount)
{
if(a[i]%2)
swap(a[i++],a[i_o++]);
else
swap(a[i++],a[i_e++]);
if (i==oddcount)
i = i_o;
}
}
int main() {
// your code goes here
int n = 20;
int *a = new int[n];
for(int i = 0; i<n; i++)
a[i] = i;
sortoddeven(a,n);
for(int i = 0; i<n; i++)
cout<<a[i]<<" ";
return 0;
}
Sorry, still seems to have some problem.
 Tuotuo March 02, 2014Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
The diff value is simply 2 times the different between the largest and the smallest num of the three.
So a naive way to do this is move the pointer of array correspond to the smallest num of the three upward by one, and update, till we reach the top or find three identical number.
condition that need to be taken care of is when there is two equal number, then compare and find the smaller one of the two number which are next to the equal number in corresponding array, and update that pointer.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote
Please comment on my solution, I think it works, Thanks!
int test1s(int n)
{
int num1s = 0;
while(n%10==1)
{
n = n/10;
num1s++;
}
if( n == 0 )
return num1s;
else
return 0;
}
string minmul3(int n)
{
string err = "err";
if (mod(n+10,10)!=3)
return err;
//we are solving the problem by iterative find the digit of b,which satisfies n*b=111....11.
//pre recomputed map[i] = s; st: mod(s*3+i,10) = 1;
int map[] = {7,0,3,6,9,2,5,8,1,4};
int res =0;
int count = 0;
while (test1s(res)==0)
{
count++;
int b = map[res%10];
res = res/10 + b*n;
}
count = count + test1s(res);
string result;
result.resize(count+1);
memset(result.c_str(),'1',count);
result.c_str()[count+1] = 0;
return result;
}

Tuotuo
August 10, 2013 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
Implementation and Test code.
This one is O(n) complexity,
 Tuotuo January 11, 2015