# Help needed in past American Express Hiring Challenge

Hiii,
Can anyone help me in a problem asked in past American Express Hiring challenge in Hackerearth. The question named Difference between Arrays. Can anyone please help me in this one? Anyone @ssjgz @l_returns @aryanc403

1 Like

What have you tried so far?

Edit:

``````1
2
1025 1024
``````

? What useful observations can be made from this testcase?

Sample Case:

1
2
1 2

Output:
0

Oh, I missed a bit of the question. Whoops

1 Like

Can you help me out ?

Not at the moment - I misread the question initially, and have no idea how to solve the correct one, yet

I am not very sure about correctness but if not 100% correct then
I believe it is surely a good optimization algorithm.
Let me know if you can find any counter case.
@ssjgz @aryanc403 @rocky_1234
Algorithm :

1. Make all elements even ( multiply by 2 if its odd).
2. Count power of 2 in each of them and store in another array Lets say â€ścnt[]â€ť. Also make all of them odd. (divide until it becomes odd)
3. Pick minimum element
4. If count of min element is non zero then multiply it by 2 and decrease value of cnt.
5. Repeat from step 3 (if count of min element is not zero).

Answer is min of all (max_element-min_element) for each distinct array generated during this process.

3 Likes

Correct me if Iâ€™m wrong.
@ssjgz @aryanc403 @rocky_1234
divide the no until it become odd then take diff(max(a[i])-min(a[i])) for all 1<=i<=n .
Please provide counter example if this algorithm is wrong so that i can understand properly.
thanksâ€¦

This is not correct.
1
2
10 11

or
1
2
20 11

1 Like

Maybe this might work:

for every element x insert it in an array, if it is even insert x/2, x/4 â€¦so on up until it is odd.

sort the array.

for every consecutive element calculate the difference and find the minimum.

PS: we dont multiply by 2 because it will only result in a bigger difference.

Someone please tell me if this approach is correct or not.

2 Likes

Thanks for correcting meâ€¦

incorrect.
4 13 17

now you will make it
1 2 4 13 17
and You will answer 2-1 = 1

2 Likes

Seems like, No one is even reading this lol.

Thank you so much

1 Like

I did I think Iâ€™ve solved it, using your basic idea, but upside down

Basically, make sure everything is even, then repeatedly divide the maximum element by two (if we can) or break (if we canâ€™t).

Seems to survive randomised testing so far.

Edit:

Very rough code - brute force solution; optimised solution based on l_returnâ€™s idea; and testcase generator:

``````//#define SUBMISSION
#define BRUTE_FORCE
#ifdef SUBMISSION
#undef BRUTE_FORCE
#define NDEBUG
#endif
#include <iostream>
#include <vector>
#include <limits>
#include <set>
#include <map>
#include <algorithm>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

template <typename T>
{
assert(cin);
}
int solveBruteForce(const vector<int>& a)
{
int minMaxDifference = std::numeric_limits<int>::max();

set<vector<int>> toExplore = { a };
set<vector<int>> alreadySeen = { a };

while (!toExplore.empty())
{

set<vector<int>> nextToExplore;
for (const auto& x : toExplore)
{
const int difference = *max_element(x.begin(), x.end()) - *min_element(x.begin(), x.end());
if (difference < minMaxDifference)
{
cout << "New best: diff: " << difference << endl;
for (const auto a : x)
{
cout << a << " ";
}
cout << endl;

minMaxDifference = difference;
}

for (int i = 0; i < x.size(); i++)
{
vector<int> nextX = x;
if (nextX[i] % 2 == 0)
{
nextX[i] = nextX[i] / 2;
}
else
{
nextX[i] = nextX[i] * 2;
}

{
nextToExplore.insert(nextX);
}
}
}
toExplore = nextToExplore;
}

return minMaxDifference;
}

#if 1
int solveOptimised(const vector<int>& a)
{
// Minor adaption of l_return's algorithm.
int minMaxDifference = std::numeric_limits<int>::max();

map<int, int> numOfElement;
for (auto x : a)
{
if (x % 2 == 1)
{
x = x * 2;
}
numOfElement[x]++;
}

while (true)
{
cout << "Current set: " << endl;
for (const auto x : numOfElement)
{
cout << x.first << " x " << x.second << endl;
}
const int maxElement = std::prev(numOfElement.end())->first;
const int minElement = numOfElement.begin()->first;

cout << "maxElement: " << maxElement << " minElement: " << minElement << " diff: " << (maxElement - minElement) << endl;
minMaxDifference = min(minMaxDifference, maxElement - minElement);

if (maxElement % 2 == 0)
{
numOfElement[maxElement]--;
if (numOfElement[maxElement] == 0)
numOfElement.erase(std::prev(numOfElement.end()));
numOfElement[maxElement / 2]++;
}
else
{
break;
}
}

return minMaxDifference;
}
#endif

int main(int argc, char* argv[])
{
ios::sync_with_stdio(false);
if (argc == 2 && string(argv[1]) == "--test")
{
struct timeval time;
gettimeofday(&time,NULL);
srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
const int T = 1;
cout << T << endl;

for (int t = 0; t < T; t++)
{
const int N = 2 + rand() % 10;
const int maxA = rand() % 1000 + 1;

cout << N << endl;
for (int i = 0; i < N; i++)
{
cout << (1 + rand() % maxA);
if (i != N - 1)
cout << " ";
}
cout << endl;

}

return 0;
}

for (int t = 0; t < T; t++)
{
vector<int> a(N);
for (auto& value : a)

#ifdef BRUTE_FORCE
#if 1
const auto solutionBruteForce = solveBruteForce(a);
cout << "solutionBruteForce: " << solutionBruteForce << endl;
#endif
#if 1
const auto solutionOptimised = solveOptimised(a);
cout << "solutionOptimised:  " << solutionOptimised << endl;

assert(solutionOptimised == solutionBruteForce);
#endif
#else
const auto solutionOptimised = solveOptimised();
cout << solutionOptimised << endl;
#endif
}

assert(cin);
}
``````
5 Likes
1. Generate all possible numbers at each index, store it as (number, index)
2. Sort the pairs
3. Use two pointers to find minimum difference (you need to find minimum length which contains all indices)
Complexity would be O(n*log(n)) as maximum log(n) numbers are possible at each index
3 Likes

Brilliant - itâ€™s one of those cool solutions where I think â€śPfff â€¦ thatâ€™s obviously wrong â€¦ â€¦ â€¦ isnâ€™t it???â€ť

``````#define SUBMISSION
#define BRUTE_FORCE
#ifdef SUBMISSION
#undef BRUTE_FORCE
#define NDEBUG
#endif
#include <iostream>
#include <vector>
#include <limits>
#include <set>
#include <map>
#include <algorithm>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

template <typename T>
{
assert(cin);
}
int solveBruteForce(const vector<int>& a)
{
int minMaxDifference = std::numeric_limits<int>::max();

set<vector<int>> toExplore = { a };
set<vector<int>> alreadySeen = { a };

while (!toExplore.empty())
{

set<vector<int>> nextToExplore;
for (const auto& x : toExplore)
{
const int difference = *max_element(x.begin(), x.end()) - *min_element(x.begin(), x.end());
if (difference < minMaxDifference)
{
cout << "New best: diff: " << difference << endl;
for (const auto a : x)
{
cout << a << " ";
}
cout << endl;

minMaxDifference = difference;
}

for (int i = 0; i < x.size(); i++)
{
vector<int> nextX = x;
if (nextX[i] % 2 == 0)
{
nextX[i] = nextX[i] / 2;
}
else
{
nextX[i] = nextX[i] * 2;
}

{
nextToExplore.insert(nextX);
}
}
}
toExplore = nextToExplore;
}

return minMaxDifference;
}

int solveOptimised(const vector<int>& a)
{
// mishraanoopam's algorithm from https://discuss.codechef.com/t/help-needed-in-past-american-express-hiring-challenge/45082/16
int minMaxDifference = std::numeric_limits<int>::max();
struct TransformedValueAndIndex
{
int value = -1;
int originalIndex = -1;
};

vector<TransformedValueAndIndex> valuesAndIndices;
for (int i = 0; i < a.size(); i++)
{
int value = a[i];
// Build up the full set of values that can be created, using the given rules,
// from a[i], and add them to valuesAndIndices.
if (value % 2 == 1)
{
value = value * 2;
}
while (value % 2 == 0)
{
valuesAndIndices.push_back({value, i});
value = value / 2;
}
valuesAndIndices.push_back({value, i});
}
sort(valuesAndIndices.begin(), valuesAndIndices.end(), [](const auto& lhs, const auto& rhs) { return lhs.value < rhs.value; });

// Two pointers - for each leftIndex (in valuesAndIndices array), find the minimum rightIndex such
// that the set { valuesAndIndices[j].originalIndex | leftIndex <= j <= rightIndex } is the set of n
// original indices 0, 1, 2, ... n ( = a.size())
int leftIndex = 0;
map<int, int> numOfOriginalIndexInRange;
numOfOriginalIndexInRange[valuesAndIndices[leftIndex].originalIndex]++;
int numOriginalIndicesInRange = 1;
int rightIndex = 0;
while (leftIndex < valuesAndIndices.size())
{
while (rightIndex < valuesAndIndices.size() && numOriginalIndicesInRange < a.size())
{
rightIndex++;
numOfOriginalIndexInRange[valuesAndIndices[rightIndex].originalIndex]++;
if (numOfOriginalIndexInRange[valuesAndIndices[rightIndex].originalIndex] == 1)
numOriginalIndicesInRange++;
}
if (rightIndex == valuesAndIndices.size())
break;

minMaxDifference = min(minMaxDifference, valuesAndIndices[rightIndex].value - valuesAndIndices[leftIndex].value);

numOfOriginalIndexInRange[valuesAndIndices[leftIndex].originalIndex]--;
if (numOfOriginalIndexInRange[valuesAndIndices[leftIndex].originalIndex] == 0)
numOriginalIndicesInRange--;
leftIndex++;
}
return minMaxDifference;
}

int main(int argc, char* argv[])
{
ios::sync_with_stdio(false);
if (argc == 2 && string(argv[1]) == "--test")
{
struct timeval time;
gettimeofday(&time,NULL);
srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
const int T = 1;
cout << T << endl;

for (int t = 0; t < T; t++)
{
const int N = 2 + rand() % 10;
const int maxA = rand() % 1000 + 1;

cout << N << endl;
for (int i = 0; i < N; i++)
{
cout << (1 + rand() % maxA);
if (i != N - 1)
cout << " ";
}
cout << endl;

}

return 0;
}

for (int t = 0; t < T; t++)
{
vector<int> a(N);
for (auto& value : a)

#ifdef BRUTE_FORCE
#if 1
const auto solutionBruteForce = solveBruteForce(a);
cout << "solutionBruteForce: " << solutionBruteForce << endl;
#endif
#if 1
const auto solutionOptimised = solveOptimised(a);
cout << "solutionOptimised:  " << solutionOptimised << endl;

assert(solutionOptimised == solutionBruteForce);
#endif
#else
const auto solutionOptimised = solveOptimised(a);
cout << solutionOptimised << endl;
#endif
}

assert(cin);
}
``````

Edit:

Now with Diagnostic Outputâ„˘:

``````#define SUBMISSION
#define BRUTE_FORCE
#ifdef SUBMISSION
#undef BRUTE_FORCE
//#define NDEBUG
#endif
#include <iostream>
#include <vector>
#include <limits>
#include <set>
#include <map>
#include <algorithm>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

template <typename T>
{
assert(cin);
}
int solveBruteForce(const vector<int>& a)
{
int minMaxDifference = std::numeric_limits<int>::max();

set<vector<int>> toExplore = { a };
set<vector<int>> alreadySeen = { a };

while (!toExplore.empty())
{

set<vector<int>> nextToExplore;
for (const auto& x : toExplore)
{
const int difference = *max_element(x.begin(), x.end()) - *min_element(x.begin(), x.end());
if (difference < minMaxDifference)
{
cout << "New best: diff: " << difference << endl;
for (const auto a : x)
{
cout << a << " ";
}
cout << endl;

minMaxDifference = difference;
}

for (int i = 0; i < x.size(); i++)
{
vector<int> nextX = x;
if (nextX[i] % 2 == 0)
{
nextX[i] = nextX[i] / 2;
}
else
{
nextX[i] = nextX[i] * 2;
}

{
nextToExplore.insert(nextX);
}
}
}
toExplore = nextToExplore;
}

return minMaxDifference;
}

int solveOptimised(const vector<int>& a)
{
// mishraanoopam's algorithm from https://discuss.codechef.com/t/help-needed-in-past-american-express-hiring-challenge/45082/16
int minMaxDifference = std::numeric_limits<int>::max();
struct TransformedValueAndIndex
{
int value = -1;
int originalIndex = -1;
};

vector<TransformedValueAndIndex> valuesAndIndices;
for (int i = 0; i < a.size(); i++)
{
int value = a[i];
// Build up the full set of values that can be created, using the given rules,
// from a[i], and add them to valuesAndIndices.
if (value % 2 == 1)
{
value = value * 2;
}
while (value % 2 == 0)
{
valuesAndIndices.push_back({value, i});
value = value / 2;
}
valuesAndIndices.push_back({value, i});
}
sort(valuesAndIndices.begin(), valuesAndIndices.end(), [](const auto& lhs, const auto& rhs) { return lhs.value < rhs.value; });

// Two pointers - for each leftIndex (in valuesAndIndices array), find the minimum rightIndex such
// that the set { valuesAndIndices[j].originalIndex | leftIndex <= j <= rightIndex } is the set of n
// original indices 0, 1, 2, ... n ( = a.size())
int leftIndex = 0;
map<int, int> numOfOriginalIndexInRange;
numOfOriginalIndexInRange[valuesAndIndices[leftIndex].originalIndex]++;
int numOriginalIndicesInRange = 1;
int rightIndex = 0;

int bestLeftIndex = -1;
int bestRightIndex = -1;
while (leftIndex < valuesAndIndices.size())
{
while (rightIndex < valuesAndIndices.size() && numOriginalIndicesInRange < a.size())
{
rightIndex++;
numOfOriginalIndexInRange[valuesAndIndices[rightIndex].originalIndex]++;
if (numOfOriginalIndexInRange[valuesAndIndices[rightIndex].originalIndex] == 1)
numOriginalIndicesInRange++;
}
if (rightIndex == valuesAndIndices.size())
break;

const int maxDifference = valuesAndIndices[rightIndex].value - valuesAndIndices[leftIndex].value;
if (maxDifference < minMaxDifference)
{
bestLeftIndex = leftIndex;
bestRightIndex = rightIndex;

minMaxDifference = maxDifference;
}

numOfOriginalIndexInRange[valuesAndIndices[leftIndex].originalIndex]--;
if (numOfOriginalIndexInRange[valuesAndIndices[leftIndex].originalIndex] == 0)
numOriginalIndicesInRange--;
leftIndex++;
}

{
// Diagnostics.
vector<int> newValueAtOriginalIndex(a.size());
set<int> originalIndicesUsed = { valuesAndIndices[bestLeftIndex].originalIndex, valuesAndIndices[bestRightIndex].originalIndex };
newValueAtOriginalIndex[valuesAndIndices[bestLeftIndex].originalIndex] = valuesAndIndices[bestLeftIndex].value;
newValueAtOriginalIndex[valuesAndIndices[bestRightIndex].originalIndex] = valuesAndIndices[bestRightIndex].value;
assert(valuesAndIndices[bestLeftIndex].originalIndex != valuesAndIndices[bestRightIndex].originalIndex);
for (int i = bestLeftIndex + 1; i <= bestRightIndex - 1; i++)
{
const int originalIndex = valuesAndIndices[i].originalIndex;
if (originalIndicesUsed.find(originalIndex) == originalIndicesUsed.end())
{
originalIndicesUsed.insert(originalIndex);
newValueAtOriginalIndex[originalIndex] = valuesAndIndices[i].value;
}
}
assert(originalIndicesUsed.size() == a.size());

vector<int> copyOfA(a);
auto printArray = [&copyOfA](int highlightIndex) {
for (int i = 0; i < copyOfA.size(); i++)
{
if (i == highlightIndex)
cout << "[";
cout << copyOfA[i];
if (i == highlightIndex)
cout << "]";
cout << " ";
}
cout << endl;
};
cout << "Starting array: " << endl;
printArray(-1);
cout << endl;
for (int i = 0; i < a.size(); i++)
{
while (newValueAtOriginalIndex[i] > copyOfA[i])
{
assert(copyOfA[i] % 2 == 1);
cout << "Double the odd value " << copyOfA[i] << " at index " << i << " giving " << copyOfA[i] * 2 << endl;
copyOfA[i] *= 2;
printArray(i);
cout << endl;
}
while (newValueAtOriginalIndex[i] < copyOfA[i])
{
assert(copyOfA[i] % 2 == 0);
cout << "Halve the even value " << copyOfA[i] << " at index " << i << " giving " << copyOfA[i] / 2 << endl;
copyOfA[i] /= 2;
printArray(i);
cout << endl;
}
assert(copyOfA[i] == newValueAtOriginalIndex[i]);

}
const int difference = *max_element(copyOfA.begin(), copyOfA.end()) - *min_element(copyOfA.begin(), copyOfA.end());
assert(difference == minMaxDifference);
}

return minMaxDifference;
}

int main(int argc, char* argv[])
{
ios::sync_with_stdio(false);
if (argc == 2 && string(argv[1]) == "--test")
{
struct timeval time;
gettimeofday(&time,NULL);
srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
const int T = 1;
cout << T << endl;

for (int t = 0; t < T; t++)
{
const int N = 2 + rand() % 10;
const int maxA = rand() % 1000 + 1;

cout << N << endl;
for (int i = 0; i < N; i++)
{
cout << (1 + rand() % maxA);
if (i != N - 1)
cout << " ";
}
cout << endl;

}

return 0;
}

for (int t = 0; t < T; t++)
{
vector<int> a(N);
for (auto& value : a)

#ifdef BRUTE_FORCE
#if 1
const auto solutionBruteForce = solveBruteForce(a);
cout << "solutionBruteForce: " << solutionBruteForce << endl;
#endif
#if 1
const auto solutionOptimised = solveOptimised(a);
cout << "solutionOptimised:  " << solutionOptimised << endl;

assert(solutionOptimised == solutionBruteForce);
#endif
#else
const auto solutionOptimised = solveOptimised(a);
cout << solutionOptimised << endl;
#endif
}

assert(cin);
}
``````
4 Likes

In which case it is failing ? I guess it works well

Itâ€™s not - or at least, it passes 10â€™000 randomised testcases It looked like it wouldnâ€™t work to me, though, when I first read it

4 Likes

No i guess it worked for 1000 random cases when i tested

2 Likes