mahadev
BAN USERHere is the logic:
Basically, sorting means arrangement of number. To do so we need to swap numbers based on some condition...
Below is the logic of that condition...
we have 2 numbers lets say
94 and 9
calculate number of digits. which are 2 and 1 respectively.
then
inumber = 9*(10^2)+94;
jnumber = 94*(10^1)+9;
compare above numbers and then make decision of swapping....
I hope it helps....
radix sort won't work...
here we need to decide if we want to swap numbers or not
int numdigit(int ip)
{
int recnt = 0;
while(ip > 0)
{
recnt++;
ip /=10;
}
return recnt;
}
bool isSwapNeeded(int i,int j)
{
int iposnum = i*pow(10,numdigit(j))+j;
int jposnum = j*pow(10,numdigit(i))+i;
return iposnum < jposnum;
}

mahadev
October 11, 2012 logic::
while traversing array,
use 2 bool variables,
bprev => relation [ascending/descending] between current & prev elements i.e.a[i1] & a[i]
bcur => relation [ascending/descending] between current & next elements i.e.a[i1] & a[i]
if bprev == bcur
increment counter
else
there is change, so prevcounter = max of curcounter and prev counter
curcounter ++
return max counter +1
code
#include "iostream"
using namespace std;
int maxAscDeslength(int a[],int n)
{
int prevcounter =0 ,curcounter = 0;
bool bprev = true;
if(a[0] > a[1])
bprev = false;
bool bcur;
for(int i =0; i< n1; ++i)
{
if(a[i] < a[i+1])
bcur = true;
else
bcur = false;
if(bprev != bcur)
{
prevcounter = max(prevcounter,curcounter);
curcounter = 1;
}
else
curcounter++;
bprev = bcur;
}
return (max(curcounter,prevcounter)+1);
}
int main (){
int a[] = {3, 5, 8 , 9, 3, 1, 4, 5, 6};
cout << maxAscDeslength(a,9);
return 0;
}

mahadev
September 26, 2012 haha actually i was/am not good in putting logic into code... n had failed at few companies just because of that... thats why coding :) n of course coding definitely boost confidence...
For solution of the problem w/o queue...
interesting lets see if we/other can find the solution...
logic:
BFS traversal while popping element from queue. push it on stack.
#include <queue>
#include <stack>
#include <vector>
#include "iostream"
using namespace std;
#define EOFlevel 1
extern class Node
{
public:
int _data;
Node * _left;
Node * _right;
public:
Node(int val = 0){
_data = val;}
};
extern void BFSDownUp(Node * proot)
{
Node* pnode = proot;
if(pnode == 0)
return;
queue <Node *> q;
stack <Node *> stk;
q.push(pnode);
q.push(new Node(EOFlevel));
while(!q.empty())
{
Node * ptemp = q.front();
stk.push(ptemp);
q.pop();
if(q.front()>_data == EOFlevel)
{
stk.push(q.front());
q.pop();
}
if(ptemp>_left)
{
q.push(ptemp>_left);
}
if(ptemp>_right)
q.push(ptemp>_right);
if(stk.top()>_data == EOFlevel)
q.push(new Node(EOFlevel));
}
while(!stk.empty())
{
if(stk.top()>_data == EOFlevel)
{
cout << endl;
}
else
{
cout << stk.top()>_data << "==";
}
stk.pop();
}
}

mahadev
September 18, 2012 //logic
// loop on input array
// //STEP A calculate product
// count number of 0 in numzero
// if numzero > 1 break;
// Also, calculate prod = product of all elements excluding 0
// //STEP B determine output array element based on num zero
// if numzero > 1
// all elements of out array are 0
// else if numzero == 1
// if(input[i] == 0)
// output[i] = prod
// else
// output[i] = 0
// else if numzero == 0
// output[i] = prod/input[i];
#include "iostream"
using namespace std;
void Mularray(int in[],int out[],int size)
{
int numberOfZero= 0;
int prod = 1;
for(int i = 0; i < size; ++i)
{
if(in[i] == 0)
{
++numberOfZero;
if(numberOfZero >1)
break; // No need to traverse all out elements are 0
}
else
prod = prod * in[i];
}
if(numberOfZero > 1)
{
for(int i = 0; i < size ; ++i)
{
out[i] = 0;
}
}
else if(numberOfZero ==1)
{
for(int i = 0; i < size; ++i)
{
if(in[i] == 0)
out[i] =prod;
else
out[i] = 0;
}
}
else //numberOfZero == 0
{
for(int i = 0; i < size; ++i)
out[i] = prod/in[i];
}
}
void print(int a[],int size)
{
for(int i = 0 ;i < size;++i)
{
cout << a[i] << "==>";
}
}
int main ()
{
int a[] = {3,4,0,6,5};
print(a,5);
cout << endl;
cout << endl;
int b[5] ;
Mularray(a,b,5);
print(b,5);
return 0;
}

mahadev
September 18, 2012 //Logic
//
//For entire array.
//1. check if at current position correct number is placed
// if yes then continue
// if NOT then follow 2 to 5
//2. find the position of the correct number let this position be jposition
//3. store jpositionth number in temp
//4. shift array from current position to jposition
//5. store temp at current position...
//code
#include "iostream"
using namespace std;
void print(int a[],int size)
{
for (int i =0;i<size;i++)
cout << a[i] << "==>";
}
void ArrangeArrayEvenOdd(int a[],int size)
{
for(int i = 0; i<9; ++i)
{
//step 1
if(i%2 == a[i]%2)
continue;
else
{//step2
int j = 1+i;
if(i%2 ==0)
{
while(a[j]%2 != 0)
++j;
}
else
{
while(a[j]%2 !=1)
++j;
}
//step 3
int temp = a[j];
//step 4 shifting array
int k = j;
while(k>i)
{
a[k] = a[k1];
k;
}
//step 5 correct element at correct position
a[i] = temp;
}
}
}
int main ()
{
int a[] = {1,5,7,2,3,8,6,0,10};
print(a,9);
cout << endl;
cout << endl;
ArrangeArrayEvenOdd(a,9);
print(a,9);
return 0;
}

mahadev
September 17, 2012 Open Chat in New Window
I assume you need to use std::unordered_map instead of std::map.
 mahadev July 08, 2014unordered_map stores data in the form of hash tables(lookup O(constant), O(n) in worst case). In contrast, map stores data in the form of red black tree (lookup O(logn))