Loops Posted Sep 12, 2020

Imagine you are given a number n. You need to find out all possible sets of numbers that fit into a,b,c,d such that a3+b3=c3+d3. There is no restriction that the numbers a,b,c,d need to be distinct.

Let's ask ourselves a question; what do we have? and what do we need to find? The one we have is a limit n. And the one we need to find all sets of numbers which satisfy that equality.

Let's say for example, we have our input limit as 5. What are all the possible numbers which can satisfy that equality? Let's assume we put a =1 and b=2 there. a3+b3 = 1+8 = 9. Which two numbers within 5 which form the same equality?

By commutative principle of addition (there's a math rule), a+b = b+a. And so, for the numbers which make a3+b3, the other numbers which satisfy the equality are obviously b and a.

Coming back to the question. We can implement this in two approaches: the inefficient but basic approach : where we possibly place all the values of a,b,c under n and find the last number d such that d = cuberoot(a3+b3-c3)

the code can look something like this:

```
function powerOfNumber(num, exp) {
return Math.pow(num, exp);
}
function sumByThreeLoops(n) {
for (var a = 1; a <= n; a++) {
for (var b = 1; b <= n; b++) {
for (var c = 1; c <= n; c++) {
var a3 = powerOfNumber(a, 3);
var b3 = powerOfNumber(b, 3);
var c3 = powerOfNumber(c, 3);
var d = Math.round(powerOfNumber(a3 + b3 - c3, 1 / 3));
if (d <= n) {
console.log(`a=${a}, b=${b}, c=${c}, d=${d}`);
}
}
}
}
}
```

While this approach does the job, its highly inefficient. The complexity of this one is O(n3) since we're using three nested loops in getting our job done.

Is there any other way? The efficient approach would be like this:

- Iterate through the first two numbers a, b and compute their sum of cubes.
- Store the values generated for every such sum as a key and the pairs of a, b which generated such values as a value containing list of pairs.
- Once this Table is ready, just loop through each of these generated keys and print the values of a,b - those are the numbers on the other side as well (c,d) which together form the equality

```
function sumOfPowers(n, sumPairs) {
for (var c = 1; c <= n; c++) {
for (var d = 1; d <= n; d++) {
var c3 = powerOfNumber(c, 3);
var d3 = powerOfNumber(d, 3);
var key = c3 + d3;
if (!sumPairs.hasOwnProperty(key))
sumPairs[key] = [];
else if (sumPairs.hasOwnProperty(key)) {
var pairs = sumPairs[key];
sumPairs[key].push(c);
sumPairs[key].push(d);
}
}
}
return sumPairs;
}
function sumByTwoLoops(n) {
var sumPairs = {};
// fill a3+b3
sumPairs = sumOfPowers(n, sumPairs);
for (var key in sumPairs) {
var pairs = sumPairs[key];
console.log(pairs);
}
}
```

Enjoy this article?
*Buy Me a Coffee*

Join the community! Like on Facebook Follow on Twitter

Compute and generate a compressed string for a given string containing repetitions

Find all possible natural numbers below a given limit such that a3+b3 = c3+d3

Find all the pairs in a given ordered set of numbers whose sum is equal to a given input sum

Find all the pairs in a given unordered set of numbers whose sum is equal to a given input sum

Sort the given unordered set of Binary digits

(UPDATED to .NET 6) Implementing CQRS with MediatR in ASP.NET Core

(UPDATED to .NET 6) Calling Stored Procedures in ASP.NET Core / EF Core

(UPDATED to .NET 5) Integrating OData with ASP.NET Core Web API

Integrating MongoDB with ASP.NET Core (.NET 6)

Implementing Role based and Claims based Authorization in ASP.NET Core (.NET 5)