sid1505
BAN USER#include<iostream>
int main()
{
char szStr[] = "abcbac";
int i = 0;
int j = 0;
while (szStr[j])
{
if (szStr[j] == 'b'  (szStr[j] == 'a' && szStr[j + 1] && szStr[j + 1] == 'c'))
{
if (szStr[j] == 'a')
{
j++;
}
}
else
{
if (i != j)
{
szStr[i] = szStr[j];
}
i++;
}
j++;
}
szStr[i] = '\0';
std::cout << "String after removing b and ac is " << szStr << std::endl;
return 0;
}

sid1505
September 28, 2015 This can be solved by traversing the array and keeping two indexes i and j to point to location where next 0 and 2 is going to be placed.
Code is given below :
// Sort an array containing 0s, 1s and 2s.cpp : Defines the entry point for the console application.
// Program to sort an array containing 0s, 1s and 2s only
#include<iostream>
void swap(int* num1, int* num2)
{
int nTemp = *num1;
*num1 = *num2;
*num2 = nTemp;
}
int main()
{
int nArray[] = {1, 2, 0, 0, 1, 2, 2, 2, 1, 1, 0, 0, 2, 1, 1};
int nLength = sizeof(nArray) / sizeof(int);
int i = 0;
int j = nLength  1;
int k = 0;
while(k < j)
{
if(nArray[k] == 0)
{
if(k != i)
{
swap(nArray + i, nArray + k);
}
k++;
i++;
}
else if(nArray[k] == 2)
{
swap(nArray + j, nArray + k);
j;
}
else
{
k++;
}
}
std::cout << "Array after segegating 0s, 1s and 2s\n";
for(int i = 0; i < nLength; i++)
{
std::cout << nArray[i] << std::endl;
}
return 0;
}

sid1505
September 06, 2015 This can be done by comparing only a single time as described below :
Pseudo code :
int bSearch(int nArray[], int nLength, int nVal)
//
int nRes < 1
int nStart < 0
int nEnd < nLength  1
while nStart <= nEnd
do
 int nMid < (nStart + nEnd) / 2
 if nVal > nArray[nMid]
 then
  nEnd < nMid  1
 else
  nRes < nMid
  nStart < nMid + 1
return nRes
There are many ways to solve this problem. They are described below :
1. Sorting  Sort both the arrays. Now use two iterators to traverse through each element of both the arrays. Adjust the iterators after every traversal and print the common elements.
Pseudo Code :
void intersection(int nArray1[], int nLength1, int nArray2[], int nLength2)
//
sort(nArray1, nLength1)
sort(nArray2, nLength2)
int i < 0
int j < 0
while i < nLength1 && j < nLength2
do
 if nArray1[i] is equal to nArray2[j]
then
  print nArray1[i]
  i++
  j++
 else if nArray1[i] < nArray2[j]
  i++
 else
  j++
Complexity : O(nlogn + mlogm)
2. Sort the smaller array and use binary search for each element in the larger array.
It has better complexity than the 1st method.
void intersection(int nArray1[], int nLength1, int nArray2[], int nLength2)
//
sort(nArray2, nLength2) // Imagining that second array is smaller
int i < 0
while i < nLength1
do
 if nArray1[i] is found in nArray2 by binary search method
 then
  print nArray1[i]
 i++
Complexity : O(mlogm + nlogm)
3. Hashing : Store the elements of smaller array in a hash map.
Now, traverse through each and every element of first array, if the hash map exists for that element then print that element else increment the iterator.
The pseudo code is like this :
void intersection(int nArray1[], int nLength1, int nArray2[], int nLength2)
//
int i < 0
while i < nLength2
do
 hMap[nArray2[i]] < true
 i++
i < 0
while i < nLength1
do
 if hMap[nArray1[i]] exists
 then
  print nArray1[i]
 i++
Complexity : O(n + m)
Space complexity : O(m)
4. Binary Search tree : This method is same as hashing however, this time we're storing the smaller array elements in a binary search tree and then for each element in array 1 we're finding whether it's present in the tree or not.
Complexity : O(mlogm + nlogm)
Space complexity : O(m)
If Hash Table is used then the time complexity of the solution is O(n).
However, space complexity will also be O(n).
Else, we have to check by brute force and that solution is O(n ^ 2).
If we use sorting then also we need extra O(n) space, making the hash table far more easy than rest of the solutions.
There are three methods to do this :
1. Sort both the arrays and then find the intersection by comparing elements linearly.
2. Sort the smaller array, and for each element in the large array find whether the element is present in the array or not. If yes, then print the element.
3. Hashmap based solution : Store the values of B array in a hashmap, and then check for each value in A, whether it's present or not.
The simplest(yet efficient) solution for the above problem would be the one that most guys are posting here :
int min(int nArray[], int nLength)
//
int nMin < infinite
for int i < 0 to nLength  1
do
 if nArray[i] < nMin
then
  nMin < nArray[i]
return nMin
Time Complexity : O(n)
Assignment operations :
Worst case : n, where n is the length of array (Array sorted in decreasing order)
Best case : 1, Only for the first time (Array sorted in increasing order)
#include<iostream>
void swap(int* num1, int* num2)
{
int nTemp = *num1;
*num1 = *num2;
*num2 = nTemp;
}
void reverseArray(int* nArray, int nStart, int nEnd)
{
while(nStart < nEnd)
{
swap(nArray + nStart, nArray + nEnd);
nStart++;
nEnd;
}
}
int main()
{
int nArray1[] = {1, 5, 8, 9, 15};
int nArray2[8] = {2, 4, 14};
int nLength1 = sizeof(nArray1) / sizeof(int);
int nLength2 = 3;
int i = 0;
int j = 0;
int k = nLength2;
while(i < nLength1 && j < nLength2)
{
if(nArray1[i] < nArray2[j])
{
nArray2[k] = nArray1[i];
i++;
}
else
{
nArray2[k] = nArray2[j];
j++;
}
k = (k + 1) % 8;
}
while(i < nLength1)
{
nArray2[k] = nArray1[i];
i++;
k = (k + 1) % 8;
}
while(j < nLength2)
{
nArray2[k] = nArray2[j];
j++;
k = (k + 1) % 8;
}
reverseArray(nArray2, 0, nLength2  1);
reverseArray(nArray2, nLength2, 7);
reverseArray(nArray2, 0, 7);
std::cout << "Array after merging\n";
for(int i = 0; i < 8; i++)
{
std::cout << nArray2[i] << std::endl;
}
return 0;
}

sid1505
August 30, 2015 #include<iostream>
// Function prototypes
bool isSortedArrayPossible(int* nArray, int nLength);
void swap(int* num1, int* num2);
int main()
{
int nArray[] = {5, 13, 19, 22, 29, 21};
int nLength = sizeof(nArray) / sizeof(int);
if(isSortedArrayPossible(nArray, nLength))
{
std::cout << "Sorted array is possible\n";
}
else
{
std::cout << "Sorted array is not possible\n";
}
return 0;
}
// 
// Func : bool isSortedArrayPossible(int* nArray, int nLength)
// Descrip : Check whether we can get a sorted array or not
// 
bool isSortedArrayPossible(int* nArray, int nLength)
{
int i = 0;
while(i < nLength  1 && nArray[i] < nArray[i + 1])
{
i++;
}
int j = i + 1;
while(j < nLength  1 && nArray[j] < nArray[j + 1])
{
j++;
}
swap(nArray + i, nArray + j);
bool bSorted = false;
if(nArray[i] < nArray[i + 1] && (i == 0  nArray[i] > nArray[i  1]))
{
if(nArray[j] > nArray[j  1])
{
int k = j;
while(k < nLength  1 && nArray[k] < nArray[k + 1])
{
k++;
}
if(k == nLength  1)
{
bSorted = true;
}
}
}
return bSorted;
}
// 
// Func : void swap(int* num1, int* num2)
// Descrip : Swap two numbers
// 
void swap(int* num1, int* num2)
{
int nTemp = *num1;
*num1 = *num2;
*num2 = nTemp;
}
Open Chat in New Window
 sid1505 October 02, 2015