#include <iostream>

// Why does the following program seem to conclude that
// no integer is the sum of two positive cubes, even
// though, for example,
//
//     35 = 2^3 + 3^3?
//
// Try to find the bug before compiling the program.
//
// Also notice that the inner loop starts with j = i.
//
// Is this valid? Why might starting with j = i actually
// be preferable to starting with j = 1?

// Function declarations
int main();

// Function definitions
int main() {
    int n{};

    std::cout << "Enter an integer: ";
    std::cin  >> n;

    int i{};
    int j{};

    for ( i = 1; i < n; ++i ) {
        for ( j = i; j < n; ++j ) {
            if ( i*i*i + j*j*j == n ) {
                break;
            }
        }
    }

    if ( i == n ) {
        std::cout << n
                  << " is not the sum of two positive cubes."
                  << std::endl;
    } else {
        std::cout << n << " = "
                  << i << "^3 + "
                  << j << "^3"
                  << std::endl;
    }

    return 0;
}





















// Hint:
//
// What exactly happens when a 'break' statement is
// executed inside a loop?
//
// In particular, if a 'break' statement is inside
// two nested loops, does it terminate both loops or
// only one of them?
//
// As for starting the inner loop with j = i, this
// is completely valid.
//
// First, it is possible that i == j. For example,
//
//     16 = 2^3 + 2^3.
//
// Second, because addition is commutative, if we
// have already tested
//
//     5^3 + 9^3,
//
// there is no reason to later test
//
//     9^3 + 5^3.
//
// Starting with j = i ensures that i <= j and avoids
// testing the same pair twice.




























// Explanation:
//
// There are two nested for loops, but the 'break'
// statement terminates only the innermost loop that
// contains it.
//
// Therefore, when a sum of two cubes is found, the
// program exits the inner loop, but the outer loop
// continues with its next iteration.
//
// Eventually, the outer loop always terminates because
//
//     i < n
//
// becomes false. At that point, i == n.
//
// Consequently, the later test
//
//     if ( i == n )
//
// always concludes that no solution was found.
//
// We therefore need some way to remember that a
// solution was found and then terminate the outer
// loop as well.
//
// A variable of type 'bool' is useful for this.




























// Here is one solution:
/*
int main() {
    int n{};

    std::cout << "Enter an integer: ";
    std::cin  >> n;

    bool found{ false };

    int i{};
    int j{};

    for ( i = 1; i*i*i < n; ++i ) {
        for ( j = i; i*i*i + j*j*j <= n; ++j ) {
            if ( i*i*i + j*j*j == n ) {
                found = true;
                break;
            }
        }

        if ( found ) {
            break;
        }
    }

    if ( found ) {
        std::cout << n << " = "
                  << i << "^3 + "
                  << j << "^3"
                  << std::endl;
    } else {
        std::cout << n
                  << " is not the sum of two positive cubes."
                  << std::endl;
    }

    return 0;
}
*/


























// Here is another possible solution:
//
// The variable 'found' can also be included directly
// in the conditions of the two loops:
//
//     int i{};
//     int j{};
//     bool found{ false };
//
//     for ( i = 1; !found && (i*i*i < n); ++i ) {
//         for ( j = i;
//               !found && (i*i*i + j*j*j <= n);
//               ++j ) {
//             if ( i*i*i + j*j*j == n ) {
//                 found = true;
//             }
//         }
//     }
//
// There is, however, an awkward consequence.
//
// When 'found' is set to true, execution reaches the
// update expression of the inner for loop:
//
//     ++j
//
// before its condition is tested again. The inner
// loop then terminates.
//
// Execution subsequently reaches the update expression
// of the outer loop:
//
//     ++i
//
// before that condition is tested again.
//
// Thus, both 'i' and 'j' have been incremented past
// the values that produced the solution. To print
// the solution, we would have to undo these increments:
//
//     if ( found ) {
//         --i;
//         --j;
//
//         std::cout << n << " = "
//                   << i << "^3 + "
//                   << j << "^3"
//                   << std::endl;
//     } else {
//         std::cout << n
//                   << " is not the sum of two positive cubes."
//                   << std::endl;
//     }
//
// Although this approach works, the first solution is
// clearer: when a solution is found, each 'break'
// explicitly terminates the corresponding loop, and
// 'i' and 'j' retain the values that produced the
// solution.