What is Problem Reduction?
Problem reduction is an algorithm design technique that takes a complex problem and reduces it to a simpler one. The simpler problem is then solved and the solution of the simpler problem is then transformed to the solution of the original problem.
Problem reduction is a powerful technique that can be used to simplify complex problems and make them easier to solve. It can also be used to reduce the time and space complexity of algorithms.
Example:
Let’s understand the technique with the help of the following problem:
Calculate the LCM (Least Common Multiple) of two numbers X and Y.
Approach 1:
To solve the problem one can iterate through the multiples of the bigger element (say X) until that is also a multiple of the other element. This can be written as follows:
- Select the bigger element (say X here).
- Iterate through the multiples of X:
- If this is also a multiple of Y, return this as the answer.
- Otherwise, continue the traversal.
Algorithm:
Algorithm LCM(X, Y):
if Y > X:
swap X and Y
end if
for i = 1 to Y:
if X*i is divisible by Y
return X*i
end if
end for
C++
#include<bits/stdc++.h>using namespace std;// Function to find the LCM of two numbersint LCM(int x,int y) { if (y > x) { swap(x, y); // swapping the values of x and y using destructuring assignment } for (int i = 1; i <= y; i++) { if ((x*i) % y == 0) { return i*x; } } return x*y;}int main(){ int x=10, y=15; cout<<LCM(10, 15); // Output: 30} |
Python3
# codedef LCM(x, y): if y > x: x, y = y, x for i in range(1, y+1): if (x*i) % y == 0: return i*x return x*yprint(LCM(10, 15)) #Code is contributed by Siddharth Aher |
Javascript
// Function to find the LCM of two numbersfunction LCM(x, y) { if (y > x) { [x, y] = [y, x]; // swapping the values of x and y using destructuring assignment } for (let i = 1; i <= y; i++) { if ((x*i) % y === 0) { return i*x; } } return x*y;}console.log(LCM(10, 15)); // Output: 30 |
30
Time Complexity: O(Y) as the loop can iterate for maximum Y times [because X*Y is always divisible by Y]
Auxiliary Space: O(1)
Approach 2 (Problem Reduction): The above method required a linear amount of time and if the value of Y is very big it may not be a feasible solution. This problem can be reduced to another problem which is to “calculate GCD of X and Y” and the solution of that can be transformed to get the answer to the given problem as shown below:
- Calculate the GCD of X and Y using Euclid’s algorithm.
- Now we know that GCD * LCM = X*Y. So the LCM can be calculated as (X*Y/GCD).
Algorithm:
GCD (X, Y):
if X = 0:
return Y
end if
return GCD(Y%X, X)Algorithm LCM(X, Y):
G = GCD (X, Y)
LCM = X * Y / G
Python3
def gcd(x, y): if x == 0: return y return gcd(y % x, x)def lcm(x, y): g = gcd(x, y) lcm = (x*y)//g return lcmx = 10y = 15print(lcm(x, y))#Code is contributed by Siddharth Aher |
Javascript
function gcd(x, y) { if (x === 0) { return y; } return gcd(y % x, x);}function lcm(x, y) { const g = gcd(x, y); const lcm = (x * y) / g; return lcm;}const x = 10;const y = 15;console.log(lcm(x, y)); |
30
Time Complexity: O(log(min(X, Y)))
Auxiliary Space: O(1)
Must Remember points about Problem Reduction:
- Reducing a problem to another one is only practical when the total time taken for transforming and solving the reduced problem is lower than solving the original problem.
- If problem A is reduced to problem B, then the lower bound of B can be higher than the lower bound of A, but it can never be lower than the lower bound of A.
Related Articles:
- Transform and Conquer Technique
- Instance Simplification method in Transform and Conquer Technique
- Representation Change in Transform and Conquer Technique
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
