// findsumof2evens.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
/* int Find2Evens(int iLen, int* arr)
* IN: iLen - length of array
* arr - array of list
* OUT: -1 if list is empty the sum otherwise
*/
int Find2Evens(int iLen, int* arr)
{
int sum = 0;
//if there are no element in array
if((iLen == 0)|| (arr == NULL))
return -1;//no case we get the sum of 2 even nos to be -1 except in error case
//if there is only one element
if(iLen == 1)
if(arr[0]%2 == 0)
return arr[0];
int* iEven1 = NULL;
int* iEven2 = NULL;
for(int i = 0; i < iLen; i++)
{
if(arr[i]%2 == 0)
{
if((iEven1 == NULL)||(arr[i] > *iEven1))
{
iEven2 = iEven1;
iEven1 = &arr[i];
continue;
}
if(arr[i] != *iEven1)//if it a array like {1,4,4,5}
{
if((iEven2 == NULL)||(arr[i] > *iEven2))
{
iEven2 = &arr[i];
}
}
}
}
if((iEven1 == NULL)&&(iEven2 == NULL))
return -1;
if(iEven2 == NULL)
return *iEven1;
return *iEven1 + *iEven2;
}
int _tmain(int argc, _TCHAR* argv[])
{
int len = 4;
int arr[] = {1,-4,-2,7};
Find2Evens(len,arr);
return 0;
}
Friday, January 9, 2009
Find the index of first unique occurance of a character in a array - least time complexity
#include
//Complexity of the algorithm is 2n
int FindIndexOfFirstUniqueOccurance(char * arr)
{
if(arr == NULL)
return NULL;
//have a counter for each character
char iArr[256];
memset(iArr,0,256*sizeof(char));
char *ptr = arr;
while(*ptr)
{
iArr[*ptr]++;//increment the counter
ptr++;
}
ptr = arr;
while(*ptr)
{
if(iArr[*ptr] == 1)//the one that has a one set is the unique
return static_cast(ptr - arr);
ptr++;
}
return -1;
}
int _tmain(int argc, _TCHAR* argv[])
{
char * ptrarr = "abcbbcadfg";
int i = FindIndexOfFirstUniqueOccurance(ptrarr);
return 0;
}
//Complexity of the algorithm is 2n
int FindIndexOfFirstUniqueOccurance(char * arr)
{
if(arr == NULL)
return NULL;
//have a counter for each character
char iArr[256];
memset(iArr,0,256*sizeof(char));
char *ptr = arr;
while(*ptr)
{
iArr[*ptr]++;//increment the counter
ptr++;
}
ptr = arr;
while(*ptr)
{
if(iArr[*ptr] == 1)//the one that has a one set is the unique
return static_cast
ptr++;
}
return -1;
}
int _tmain(int argc, _TCHAR* argv[])
{
char * ptrarr = "abcbbcadfg";
int i = FindIndexOfFirstUniqueOccurance(ptrarr);
return 0;
}
Monday, January 5, 2009
Implementing Queue using one Stack.
class Stack
{
private:
int ar[10];
int top;
public:
Stack():top(-1){}
void Push(int i)
{
if(top <= 10)
{
ar[++top] = i;
}
}
int Pop()
{
if( !IsEmpty())
return ar[top--];
else
return -1;
}
bool IsEmpty()
{
if( top <= -1)
return true;
return false;
}
};
class Queue
{
private:
Stack st;
public:
void Enqueue(int i)
{
st.Push(i);
}
int Dequeue()
{
int iVal = st.Pop();
if(st.IsEmpty())
return iVal;
else
{
int ret = Dequeue();
st.Push(iVal);
return ret;
}
}
};
int _tmain(int argc, _TCHAR* argv[])
{
Queue q;
q.Enqueue(10);
q.Enqueue(20);
q.Enqueue(30);
int i = q.Dequeue();
i = q.Dequeue();
i = q.Dequeue();
return 0;
}
{
private:
int ar[10];
int top;
public:
Stack():top(-1){}
void Push(int i)
{
if(top <= 10)
{
ar[++top] = i;
}
}
int Pop()
{
if( !IsEmpty())
return ar[top--];
else
return -1;
}
bool IsEmpty()
{
if( top <= -1)
return true;
return false;
}
};
class Queue
{
private:
Stack st;
public:
void Enqueue(int i)
{
st.Push(i);
}
int Dequeue()
{
int iVal = st.Pop();
if(st.IsEmpty())
return iVal;
else
{
int ret = Dequeue();
st.Push(iVal);
return ret;
}
}
};
int _tmain(int argc, _TCHAR* argv[])
{
Queue q;
q.Enqueue(10);
q.Enqueue(20);
q.Enqueue(30);
int i = q.Dequeue();
i = q.Dequeue();
i = q.Dequeue();
return 0;
}
Subscribe to:
Posts (Atom)
.jpg)