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;
}
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;
}
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;
}
#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;
}
- sid1505 October 02, 2015