When More Is Less: Why 100 Lines Can Beat 2

📌Introduction:

Do you think that is it always the length of code which determines how efficient it is? Let us bust that myth with an example which explains how a well thought and logical lengthy code can beat a traditional, 2 liner code in terms of efficiency.

⚙️Problem:

You are given 9 balls and one of those balls is heavier than the rest of the group. Your task is to find out the odd ball in the least possible comparisons.

#include <iostream>
using namespace std;

int main() {
    int balls[9] = {8, 8, 8, 8, 8, 8, 8, 9, 8};

    return 0;
};

🐢Solution 1 (Short yet Inefficient):

The traditional way to solve this problem is by comparing the weights of all the balls starting from the first ball and finding out which ball has a higher weight.

The below code snippet demonstrates this solution:

#include <iostream>
using namespace std;

int main() {
    int balls[9] = {8, 8, 8, 8, 8, 8, 8, 9, 8};

    int heavyBall= arr[0];
    int heavyBallIndex;

    for(int i = 1; i < 9; i++) {
        if(balls[i] > heavyBall) {
            heavyBall = balls[i];
            heavyBallIndex = i;
        }
    }

    cout << "Heavy ball is: " << heavyBall << " and is found at index: " << heavyBallIndex << endl;

    return 0;
};

As you can see this is a small code with just few lines to write but when we dig deep into the working of this code, you’ll find out that in the worst case scenario this code will iterate through all the balls to return the answer, resulting in a total of 8 comparisons.

🐇Solution 2 (Long yet Efficient):

One other solution for finding the heavy ball is with a lengthy code and well thought logic, which is listed below:

• To find the heavier ball we can divide the 9 balls into 3 groups (G1, G2 and G3) with 3 balls in each group.

• Then we can determine the sum of all the balls within each group.

• Next, compare the sum in group 1 (G1) and group 2 (G2).

  • If G1 = G2, this means that there is no heavy ball in these groups and hence our heavy ball is in G3. In this way with just 1 comparison, we’ve eliminated 6 balls out of the total 9 balls.

• Now, we can compare the remaining 3 balls from group 3 (G3)

#include <iostream>
using namespace std;

int main() {
    int balls[9] = {8, 8, 8, 8, 8, 8, 8, 9, 8};

     int g1 = balls[0] + balls[1] + balls[2];
     int g2 = balls[3] + balls[4] + balls[5];
     int g3 = balls[6] + balls[7] + balls[8];

    if(g1 == g2) {
        if(balls[6] > balls[7])
        {
            cout << "Heavy ball is: " << balls[6] << " and is found at index: " << 7 << endl;
        }
        else if(balls[7] > balls[6])
        {
            cout << "Heavy ball is: " << balls[7] << " and is found at index: " << 8 << endl;
        }
        else {
            cout << "Heavy ball is: " << balls[8] << " and is found at index: " << 9 << endl;
        }
    }
    else if (g1 > g2) {
        if(balls[0] > balls[1])
        {
            cout << "Heavy ball is: " << balls[0] << " and is found at index: " << 1 << endl;
        }
        else if(balls[1] > balls[0])
        {
            cout << "Heavy ball is: " << balls[1] << " and is found at index: " << 2 << endl;
        }
        else {
            cout << "Heavy ball is: " << balls[2] << " and is found at index: " << 3 << endl;
        }
    }
    else {
        if(balls[3] > balls[4])
        {
            cout << "Heavy ball is: " << balls[3] << " and is found at index: " << 4 << endl;
        }
        else if(balls[4] > balls[3])
        {
            cout << "Heavy ball is: " << balls[4] << " and is found at index: " << 5 << endl;
        }
        else {
            cout << "Heavy ball is: " << balls[5] << " and is found at index: " << 6 << endl;
        }
    }

    return 0;
};

If you pay attention and count the number of comparisons in the above code you’ll find that the code only has 3 comparisons at max for any given case.

📝Conclusion (Length ≠ Efficiency):

This example explains that how a code which appears to be lengthy (for our example, 52 lines) and time consuming might actually be very efficient and faster that a code which appears to be smaller (for our example, 20 lines).