Help needed in past American Express Hiring Challenge

6

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

7

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
8

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…

9

This is not correct.
1
2
10 11

or
1
2
20 11

1 Like
10

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
11

Thanks for correcting me…

12

incorrect.
4 13 17

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

2 Likes
13

Seems like, No one is even reading this lol.

14

Thank you so much

1 Like
15

I did :slight_smile: I think I’ve solved it, using your basic idea, but upside down :slight_smile:

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>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}
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;
                }

                if (alreadySeen.find(nextX) == alreadySeen.end())
                {
                    alreadySeen.insert(nextX);
                    nextToExplore.insert(nextX);
                }
            }
        }
        toExplore = nextToExplore;
    }
    cout << "#alreadySeen: " << alreadySeen.size() << endl;

    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;
    }
    
    const auto T = read<int>();

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

#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
16
  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
17

Brilliant - it’s one of those cool solutions where I think “Pfff … that’s obviously wrong … … … isn’t it???” :slight_smile:

#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>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}
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;
                }

                if (alreadySeen.find(nextX) == alreadySeen.end())
                {
                    alreadySeen.insert(nextX);
                    nextToExplore.insert(nextX);
                }
            }
        }
        toExplore = nextToExplore;
    }
    cout << "#alreadySeen: " << alreadySeen.size() << endl;

    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;
    }
    
    const auto T = read<int>();

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

#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>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}
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;
                }

                if (alreadySeen.find(nextX) == alreadySeen.end())
                {
                    alreadySeen.insert(nextX);
                    nextToExplore.insert(nextX);
                }
            }
        }
        toExplore = nextToExplore;
    }
    cout << "#alreadySeen: " << alreadySeen.size() << endl;

    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;
    }
    
    const auto T = read<int>();

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

#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
18

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

19

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

4 Likes
20

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

2 Likes
21

Can you explain the algorithm please ? I didn’t completely get mishraanoopams.

22

I can’t really explain it much better than his original post + my code :confused: It uses one of the techniques from CAMC.

3 Likes
23

Got it…

2 Likes
24

hackerearth is so stupid that it asks same question again and again, i couldn’t blame above person who asked this question from an on going hiring event but still its fault of hackerearth.

3 Likes
25

LOL I really saw this que before and hence I answered this post.

2 Likes