How to Optimize Solutions for Coding Problems

Example: Print all positive integer solutions to the equation a^3 + b^3 = c^3 + d^3 and a, b, c, d are integers between 1 and 1000.

 

1. A brute force solutions

n = 1000

n = 1000
for a from 1 to n
	for b from 1 to n
    	for c from 1 to n
        	for d from 1 to n
            	if a^3 + b^3 = c^3 + d^3
                	print a, b, c, d

This returns O(n^4)

 

To optimize it we can make a break when we find it

n = 1000
for a from 1 to n
	for b from 1 to n
    	for c from 1 to n
        	for d from 1 to n
            	if a^3 + b^3 = c^3 + d^3
                	print a, b, c, d
                    break

However, it will not optimize much. It's still O(n^4)

 

1. Remove Unnecessary Work

To optimize, we can use math. d = sqrt of 3 (a^3 + b^3 + c^3)

n = 1000
for a from 1 to n
	for b from 1 to n
    	for c from 1 to n
        	d = pow(a^3 + b^3 - c^3, 1/3)
            if a^3+b^3 == c^3+d^3 && 0<= d && d <= n
            	print a, b, c, d
                break

It will reduce the runtime from O(N^4) to O(N^3)

 

2. Remove Duplicated Work

We can now use the pairs. We can just use a map to find it. We can even use the Hash Table.

n = 1000
for a from 1 to n
	for b from 1 to n
    	result = c^3 + d^3
        append (c,d) to list at value map[result]

for a from 1 to n
	for b from 1 to n
    	result = a^3+b^3
        list = map.get(result)
        for each pair in list
        	print a, b, pair

Once we have the map of all the (c, d) pairs, we can just use that directly. We don't need to generate the (a,b) pairs. Each (a, b) will already be in the map.

 

(Remove the duplicated storage)

n = 1000
for a from 1 to n
	for b from 1 to n
    	result = c^3 + d^3
        append (c,d) to list at value map[result]

for each result list in map
	for each pair1 in list
    	for each pair2 in list
        	print pair1, pair2

This will take our runtime to O(n^2)