'DSA optimisation problem from n^3 to n^2 time
The problem statement says given a positive integer "N" we have to find combination of four positive integers which add up to that number. Then print all the possible combinations. I was given the 3 sum version of this which I solved using 3 loops (N^3) then I optimized it for (N^2) then I was asked to do 4 sum that I was able to do in (N^3) as well but I was also asked to optimize it for N^2 but I am unable to do that. Any suggestions how I might be able to do that?
The input is just an integer and we have to find combination of 4 integers from 1 to N that add up to N.
My N^3 code:
let N = 5;
for (let I = 1; I <= N - 3; I++) {
for (let J = 1; J <= N - 3; J++) {
for (let K = 1; K <= N - 3; K+) {
let L = L - (I + J + K);
if (L >= 1)
console.log(I, J, K, L)
}
}
}
Output will be 1 1 1 2, 1 1 2 1, 1 2 1 1, 2 1 1 1
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
