Sumit Khedkar
BAN USER#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
// Total time complexity O(2*nlog(n)) + O(2n) + O(n) --> O(nlog(n))
int _tmain(int argc, _TCHAR* argv[])
{
string array1[] = {"asd", "efg", "lkm", "sumit", "rohit", "zxc", "awe"}; //input1
string array2[] = {"zxc", "awe", "efg", "zzx"}; // input2
vector<string> result1; // output
vector<string> result2; // output
int size1 = sizeof(array1)/sizeof(array1[0]);
sort(array1, array1 + size1); // time complexity O(nlog(n))
int size2 = sizeof(array2)/sizeof(array2[0]);
sort(array2, array2 + size2); // time complexity O(nlog(n))
int k = 0;
for (int i = 0, j = 0; i < size1 || j < size2; ) // time complexity O(2n)
{
if ( i == size1)
{
k = 1;
}
else if (j == size2)
{
k = -1;
}
else
{
k = array1[i].compare(array2[j]);
}
if (k > 0)
{
result2.push_back(array2[j]);
j++;
}
else if (k < 0)
{
result1.push_back(array1[i]);
i++;
}
else
{
i++;
j++;
}
}
for(int y = 0; y < result2.size(); y++) // time complexity O(n)
{
result1.push_back(result2[y]);
}
for(int y = 0; y < result1.size(); y++)
{
cout << result1[y].c_str() << " ";
}
int u;
cin >> u;
return 0;
}
Hi,
I tried to solve it without permutation. First sort the given array and then divide the array in two sorted vectors. Hence, the resultant sorted vectors will have minimum difference in their total sums.Then recursively I swap the elements till we get the equal sum on both the sides. I keep the vectors sorted so that it becomes easy in swapping the elements.
You can directly copy paste the following code are compile are run it. Please let me know if find any issue.
Time complexity of the following algo in average case should much less than 2^n.
// TwolistEqualSum.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
void SwapItems(vector<int> *v1, int * arry1Total, vector<int> *v2, int * array2Total, int mean)
{
if ((v1->size() == 0) || (v2->size()==0))
{
return;
}
if (*arry1Total == *array2Total)
{
return;
}
if (*arry1Total > mean)
{
int diff = *arry1Total - mean;
int i = 0;
int temp;
do
{
temp = (*v1)[i];
*arry1Total = *arry1Total - temp;
v2->push_back(temp);
v1->erase(v1->begin() + i);
*array2Total = *array2Total + temp;
if (*array2Total == *arry1Total)
{
break;
}
diff = diff - temp;
}while (v1->size() > 0 && diff > 0);
qsort(&(*v2)[0], v2->size(), sizeof(int), compare);
}
else
{
int diff = *array2Total - mean;
int i = 0;
int temp;
do
{
temp = (*v2)[i];
*array2Total = *array2Total - temp;
v1->push_back(temp);
v2->erase(v2->begin() + i);
*arry1Total = *arry1Total + temp;
if (*array2Total == *arry1Total)
{
break;
}
diff = diff - temp;
}while (v2->size() > 0 && diff > 0);
qsort(&(*v1)[0], v1->size(), sizeof(int), compare);
}
static int iteration = 0;
iteration++;
if (iteration < ((v1->size() + (v2->size()) / 2)))
{
SwapItems(v1, arry1Total, v2 , array2Total, mean);
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
const int inputSize = 22;
int input[inputSize] = {4,2,2,0,-1,1,10,3,7,15,23,20,3,9,6,199,50,50,50,49,12,2}; // assume the input and its size is known. For testing purpose just change inputSize and input array
/* Sampe input2
const int inputSize = 19;
int input[inputSize] = {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,1,10}; // assume the input and its size is known. For testing purpose just change inputSize and input array
*/
vector<int> v1, v2;
int total = 0;
cout << " Input list : ";
for (int i =0 ; i < inputSize; i++)
{
total = total + input[i];
cout << input[i] << " ";
}
cout << endl;
if (total % 2)
{
cout << " Not possible to divide the input list";
}
else
{
qsort(input, inputSize, sizeof(int), compare);
int arry1Total = 0;
int array2Total = 0;
int mean = 0;
for (int i =0 ; i < inputSize; i++)
{
if (!(i % 2))
{
v1.push_back(input[i]);
arry1Total = arry1Total + input[i];
}
else
{
v2.push_back(input[i]);
array2Total = array2Total + input[i];
}
}
mean = (arry1Total + array2Total) / 2;
SwapItems(&v1, &arry1Total, &v2, &array2Total, mean);
if (arry1Total == array2Total)
{
cout << " List 1: ";
for ( int k = 0; k < v1.size(); k++)
{
cout << v1[k] << " ";
}
cout << " : Total:" << arry1Total;
cout << endl;
cout << " List 2: ";
for ( int k = 0; k < v2.size(); k++)
{
cout << v2[k] << " ";
}
cout << " : Total:" << array2Total;
cout << endl;
}
else
{
cout << " Not possible to divide the input list";
}
}
int j;
cin >> j;
return 0;
}
- Sumit Khedkar August 01, 2016