Minimum total power consumption by both the current “+” & “-“
Given a matrix of size rows x cols called “power,” which represents the power associated with each cell in the field. There are two types of current flow in the field: “+” current starts from the top left corner, while “-” current starts from the top right corner. Both types of current can move in three directions: from a cell (i, j) to either (i + 1, j – 1), (i + 1, j), or (i + 1, j + 1). The power consumption between two cells is calculated as the absolute difference between the power values of the two cells: abs(power[i + 1][j + 1] – power[i][j]). The task is to calculate the minimum total power consumption by both the current “+” & “-” to reach the last row.
Note: At any given point (i, j), both types of current cannot occupy the same cell simultaneously, as it would cause an electric shock.
Examples:
Input: power[][] = {{2, 4}, {3, 9}}
Output: combined minimum power : 6
Explanation: The “+” current chooses the path 2 -> 3, and the “-” current chooses the path 4 -> 9. The minimum total power consumption [abs(3 – 2) + abs(9 – 4)] = 1 + 5 = 6Input: power[][] = {{2, 4, 6}, {8, 0, 10}, {6, 3, 9}}
Output: combined minimum power : 10
Explanation: The “+” current chooses the path 2 -> 0-> 3, and the “-” current chooses the path 6->10-> 9. The minimum total power consumption [abs(0 – 2) + abs(3 – 0) + abs(10 – 6) + abs(9 – 10)] = 5 + 5= 10.
Approach: To solve the problem using Recursion follow the below idea:
- As mentioned in the question, both “+” and “-” currents can move in three directions: (i + 1, j – 1), (i + 1, j), or (i + 1, j + 1). Therefore, the total combined directions will be 3 * 3 = 9. For each “+” current, there will be three possible ways for the “-” current to move. We need to consider all the possible 9 directions.
- The base case occurs when both the “+” and “-” currents reach the last row, which will be the minimum valid position. Once they reach the last row, it becomes the base case.
- Now, for all possible paths, we calculate the minimum and return it as the result.
Mathematically the recursion will look like the following:
- value = abs(power[next_i][next_j1] – power[i][j1]) + abs(power[next_i][next_J2] – power[i][j2]);
- value += totalPower(next_i, next_j1, next_j2, power, rows, cols);
- mini = min(mini, value);
- // base case { once it reaches to last row. }
- i == power.size()-1;
Steps to solve the problem:
- Build a recursive function and pass the starting row, col for both the current.
- For each (i, j) check if it’s valid or not, if it’s valid store the power consumption and call recursion for next.
- compare all the paths and take out the minimum power consumption.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int totalPower( int i, int j1, int j2, int power[][3], int rows, int cols) { // Base case: both "+" and "-" // reach the last row if (i == rows - 1) return 0; int mini = INT_MAX; // At each (i, j), there are 9 // combined possibilities 3 possibilities // for j1 (from -1 to 1), and the same // for j2 Thus, a total of 3 * 3 // possibilities for ( int k = -1; k <= 1; k++) { for ( int p = -1; p <= 1; p++) { int nextI = i + 1; int nextJ1 = j1 + k; int nextJ2 = j2 + p; // Check the validity of the // path and ensure there // is no collision if (nextI >= 0 && nextI < rows && nextJ1 >= 0 && nextJ1 < cols && nextJ2 >= 0 && nextJ2 < cols && nextJ1 != nextJ2) { int value = abs (power[nextI][nextJ1] - power[i][j1]) + abs (power[nextI][nextJ2] - power[i][j2]); // Recursively call for // the next i, j1, and j2 value += totalPower(nextI, nextJ1, nextJ2, power, rows, cols); // Take the minimum mini = min(mini, value); } } } // return the answer return mini; } // Driver code int main() { int power[][3] = { { 2, 4, 6 }, { 8, 0, 10 }, { 6, 3, 9 } }; int rows = sizeof (power) / sizeof (power[0]); int cols = sizeof (power[0]) / sizeof (power[0][0]); // Function call cout << "Combined Minimum Power: " << totalPower(0, 0, cols - 1, power, rows, cols) << endl; return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG { static int totalPower( int i, int j1, int j2, int power[][], int rows, int cols) { // Base case: both "+" and "-" // reach the last row if (i == rows - 1 ) return 0 ; int mini = Integer.MAX_VALUE; // At each (i, j), there are 9 // combined possibilities 3 possibilities // for j1 (from -1 to 1), and the same // for j2 Thus, a total of 3 * 3 // possibilities for ( int k = - 1 ; k <= 1 ; k++) { for ( int p = - 1 ; p <= 1 ; p++) { int nextI = i + 1 ; int nextJ1 = j1 + k; int nextJ2 = j2 + p; // Check the validity of the // path and ensure there // is no collision if (nextI >= 0 && nextI < rows && nextJ1 >= 0 && nextJ1 < cols && nextJ2 >= 0 && nextJ2 < cols && nextJ1 != nextJ2) { int value = Math.abs(power[nextI][nextJ1] - power[i][j1]) + Math.abs(power[nextI][nextJ2] - power[i][j2]); // Recursively call for // the next i, j1, and j2 value += totalPower(nextI, nextJ1, nextJ2, power, rows, cols); // Take the minimum mini = Math.min(mini, value); } } } // return the answer return mini; } // Driver code public static void main(String[] args) { int power[][] = { { 2 , 4 , 6 }, { 8 , 0 , 10 }, { 6 , 3 , 9 } }; int rows = power.length; int cols = power[ 0 ].length; // Function call System.out.println( "Combined Minimum Power: " + totalPower( 0 , 0 , cols - 1 , power, rows, cols)); } } // This code is contributed by Tapesh(tapeshdua420) |
Python3
def totalPower(i, j1, j2, power, rows, cols): # Base case: both "+" and "-" reach the last row if i = = rows - 1 : return 0 mini = float ( 'inf' ) # At each (i, j), there are 9 combined possibilities # 3 possibilities for j1 (from -1 to 1), and the same for j2 # Thus, a total of 3 * 3 possibilities for k in range ( - 1 , 2 ): for p in range ( - 1 , 2 ): nextI = i + 1 nextJ1 = j1 + k nextJ2 = j2 + p # Check the validity of the path and ensure there is no collision if ( 0 < = nextI < rows and 0 < = nextJ1 < cols and 0 < = nextJ2 < cols and nextJ1 ! = nextJ2 ): value = ( abs (power[nextI][nextJ1] - power[i][j1]) + abs (power[nextI][nextJ2] - power[i][j2]) ) # Recursively call for the next i, j1, and j2 value + = totalPower(nextI, nextJ1, nextJ2, power, rows, cols) # Take the minimum mini = min (mini, value) # return the answer return mini # Driver code if __name__ = = "__main__" : power = [[ 2 , 4 , 6 ], [ 8 , 0 , 10 ], [ 6 , 3 , 9 ]] rows = len (power) cols = len (power[ 0 ]) # Function call print ( "Combined Minimum Power:" , totalPower( 0 , 0 , cols - 1 , power, rows, cols)) #This code is Contributed by chinmaya121221 |
C#
using System; class MainClass { // Recursive function to calculate the combined minimum power static int TotalPower( int i, int j1, int j2, int [][] power, int rows, int cols) { // Base case: If we reach the last row, return 0 (no additional power) if (i == rows - 1) return 0; int mini = int .MaxValue; // Initialize the minimum power as the maximum possible value // Iterate through the 9 possible combinations of j1 and j2 values (-1, 0, 1) for ( int k = -1; k <= 1; k++) { for ( int p = -1; p <= 1; p++) { int nextI = i + 1; int nextJ1 = j1 + k; int nextJ2 = j2 + p; // Check the validity of the path and ensure no collision between j1 and j2 if (nextI >= 0 && nextI < rows && nextJ1 >= 0 && nextJ1 < cols && nextJ2 >= 0 && nextJ2 < cols && nextJ1 != nextJ2) { // Calculate the power difference and add it to the value int value = Math.Abs(power[nextI][nextJ1] - power[i][j1]) + Math.Abs(power[nextI][nextJ2] - power[i][j2]); // Recursively call the function for the next row and updated j1 and j2 value += TotalPower(nextI, nextJ1, nextJ2, power, rows, cols); // Update the minimum power if the current value is smaller mini = Math.Min(mini, value); } } } return mini; // Return the minimum power } // Driver code public static void Main( string [] args) { // Input power array int [][] power = new int [][] { new int [] { 2, 4, 6 }, new int [] { 8, 0, 10 }, new int [] { 6, 3, 9 } }; int rows = power.Length; // Number of rows in the power array int cols = power[0].Length; // Number of columns in the power array // Call the TotalPower function to find the combined minimum power and print the result Console.WriteLine( "Combined Minimum Power: " + TotalPower(0, 0, cols - 1, power, rows, cols)); } } |
Javascript
// Javascript code for the above approach function totalPower(i, j1, j2, power, rows, cols) { // Base case: both "+" and "-" // reach the last row if (i == rows - 1) return 0; let mini = Number.MAX_VALUE; // At each (i, j), there are 9 // combined possibilities 3 possibilities // for j1 (from -1 to 1), and the same // for j2 Thus, a total of 3 * 3 // possibilities for (let k = -1; k <= 1; k++) { for (let p = -1; p <= 1; p++) { let nextI = i + 1; let nextJ1 = j1 + k; let nextJ2 = j2 + p; // Check the validity of the // path and ensure there // is no collision if (nextI >= 0 && nextI < rows && nextJ1 >= 0 && nextJ1 < cols && nextJ2 >= 0 && nextJ2 < cols && nextJ1 != nextJ2) { let value = Math.abs(power[nextI][nextJ1] - power[i][j1]) + Math.abs(power[nextI][nextJ2] - power[i][j2]); // Recursively call for // the next i, j1, and j2 value += totalPower(nextI, nextJ1, nextJ2, power, rows, cols); // Take the minimum mini = Math.min(mini, value); } } } // return the answer return mini; } // Driver code let power = [ [2, 4, 6], [8, 0, 10], [6, 3, 9] ] let rows = power.length; let cols = power[0].length; // Function call console.log( "Combined Minimum Power: " + totalPower(0, 0, cols - 1, power, rows, cols)); // This code is contributed by ragul21 |
Combined Minimum Power: 10
Complexity Analysis:
- Time Complexity: O(3n + 3n) The above solution may try all the possiable path in worst case. Therefore time complexity of the above solution is exponential.
- Auxiliary Space: O(n) where n is recursion stack space.
Using Memoization :
Each state of the solution can be uniquely identified using three variables – rows,col1 & col2 (for both “+” and “-“) . So create a 3D array to store the value of each state to avoid recalculation of the same state.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; int columns = 0; int totalPower( int i, int j1, int j2, int power[][3], int rows, int cols, int memo[][3][3]) { // Base case: both "+" and "-" reach the last row if (i == rows - 1) return 0; // Check if the value is already calculated and stored in memo if (memo[i][j1][j2] != -1) return memo[i][j1][j2]; int mini = INT_MAX; // At each (i, j), there are 9 combined possibilities // 3 possibilities for j1 (from -1 to 1), and the same for j2 // Thus, a total of 3 * 3 possibilities for ( int k = -1; k <= 1; k++) { for ( int p = -1; p <= 1; p++) { int nextI = i + 1; int nextJ1 = j1 + k; int nextJ2 = j2 + p; // Check the validity of the path and ensure there is no collision if (nextI >= 0 && nextI < rows && nextJ1 >= 0 && nextJ1 < cols && nextJ2 >= 0 && nextJ2 < cols && nextJ1 != nextJ2) { int value = abs (power[nextI][nextJ1] - power[i][j1]) + abs (power[nextI][nextJ2] - power[i][j2]); // Recursively call for the next i, j1, and j2 value += totalPower(nextI, nextJ1, nextJ2, power, rows, cols, memo); // Take the minimum mini = min(mini, value); } } } // Store the calculated value in memo memo[i][j1][j2] = mini; // Return the answer return mini; } // Driver code int main() { int power[][3] = {{2, 4, 6}, {8, 0, 10}, {6, 3, 9}}; int rows = sizeof (power) / sizeof (power[0]); int cols = sizeof (power[0]) / sizeof (power[0][0]); columns = cols; int memo[rows][3][3]; memset (memo, -1, sizeof (memo)); // Initialize memo with -1 cout << "Combined Minimum Power: " << totalPower(0, 0, cols - 1, power, rows, cols, memo) << endl; return 0; } |
Java
import java.util.Arrays; public class MinimumCombinedPower { static int columns = 0 ; static int totalPower( int i, int j1, int j2, int [][] power, int rows, int cols, int [][][] memo) { // Base case: both "+" and "-" reach the last row if (i == rows - 1 ) return 0 ; // Check if the value is already calculated and stored in memo if (memo[i][j1][j2] != - 1 ) return memo[i][j1][j2]; int mini = Integer.MAX_VALUE; // At each (i, j), there are 9 combined possibilities // 3 possibilities for j1 (from -1 to 1), and the same for j2 // Thus, a total of 3 * 3 possibilities for ( int k = - 1 ; k <= 1 ; k++) { for ( int p = - 1 ; p <= 1 ; p++) { int nextI = i + 1 ; int nextJ1 = j1 + k; int nextJ2 = j2 + p; // Check the validity of the path and ensure there is no collision if (nextI >= 0 && nextI < rows && nextJ1 >= 0 && nextJ1 < cols && nextJ2 >= 0 && nextJ2 < cols && nextJ1 != nextJ2) { int value = Math.abs(power[nextI][nextJ1] - power[i][j1]) + Math.abs(power[nextI][nextJ2] - power[i][j2]); // Recursively call for the next i, j1, and j2 value += totalPower(nextI, nextJ1, nextJ2, power, rows, cols, memo); // Take the minimum mini = Math.min(mini, value); } } } // Store the calculated value in memo memo[i][j1][j2] = mini; // Return the answer return mini; } // Driver code public static void main(String[] args) { int [][] power = {{ 2 , 4 , 6 }, { 8 , 0 , 10 }, { 6 , 3 , 9 }}; int rows = power.length; int cols = power[ 0 ].length; columns = cols; int [][][] memo = new int [rows][ 3 ][ 3 ]; for ( int [][] arr2D : memo) { for ( int [] arr1D : arr2D) { Arrays.fill(arr1D, - 1 ); } } System.out.println( "Combined Minimum Power: " + totalPower( 0 , 0 , cols - 1 , power, rows, cols, memo)); } } |
Python3
def total_power(i, j1, j2, power, rows, cols, memo): # Base case: both "+" and "-" reach the last row if i = = rows - 1 : return 0 # Check if the value is already calculated and stored in memo if memo[i][j1][j2] ! = - 1 : return memo[i][j1][j2] mini = float ( 'inf' ) # At each (i, j), there are 9 combined possibilities # 3 possibilities for j1 (from -1 to 1), and the same for j2 # Thus, a total of 3 * 3 possibilities for k in range ( - 1 , 2 ): for p in range ( - 1 , 2 ): next_i = i + 1 next_j1 = j1 + k next_j2 = j2 + p # Check the validity of the path and ensure there is no collision if 0 < = next_i < rows and 0 < = next_j1 < cols and 0 < = next_j2 < cols and next_j1 ! = next_j2: value = abs (power[next_i][next_j1] - power[i][j1]) + abs (power[next_i][next_j2] - power[i][j2]) # Recursively call for the next i, j1, and j2 value + = total_power(next_i, next_j1, next_j2, power, rows, cols, memo) # Take the minimum mini = min (mini, value) # Store the calculated value in memo memo[i][j1][j2] = mini # Return the answer return mini # Driver code def main(): power = [[ 2 , 4 , 6 ], [ 8 , 0 , 10 ], [ 6 , 3 , 9 ]] rows = len (power) cols = len (power[ 0 ]) memo = [[[ - 1 for _ in range (cols)] for _ in range ( 3 )] for _ in range (rows)] # Initialize memo with -1 print ( "Combined Minimum Power:" , total_power( 0 , 0 , cols - 1 , power, rows, cols, memo)) if __name__ = = "__main__" : main() # This code is contributed by shivamgupta0987654321 |
C#
using System; class CombinedMinimumPower { // Method to calculate the combined minimum power recursively static int TotalPower( int i, int j1, int j2, int [,] power, int rows, int cols, int [,,] memo) { // Base case: If both "+" and "-" reach the last row, return 0 if (i == rows - 1) return 0; // Check if the result is already memoized, return the memoized value if (memo[i, j1, j2] != -1) return memo[i, j1, j2]; int mini = int .MaxValue; // Iterate through the 3x3 possible combinations for next positions for ( int k = -1; k <= 1; k++) { for ( int p = -1; p <= 1; p++) { int nextI = i + 1; int nextJ1 = j1 + k; int nextJ2 = j2 + p; // Check if the next positions are within bounds and not colliding if (nextI >= 0 && nextI < rows && nextJ1 >= 0 && nextJ1 < cols && nextJ2 >= 0 && nextJ2 < cols && nextJ1 != nextJ2) { // Calculate the cost for the current combination int value = Math.Abs(power[nextI, nextJ1] - power[i, j1]) + Math.Abs(power[nextI, nextJ2] - power[i, j2]); value += TotalPower(nextI, nextJ1, nextJ2, power, rows, cols, memo); // Recursively calculate for next positions mini = Math.Min(mini, value); // Update minimum cost } } } memo[i, j1, j2] = mini; // Memoize the minimum cost for current positions return mini; // Return the minimum value } // Initialize the memoization array with -1 static int [,,] InitializeMemo( int rows, int cols1, int cols2) { int [,,] memo = new int [rows, cols1, cols2]; for ( int i = 0; i < rows; i++) { for ( int j = 0; j < cols1; j++) { for ( int k = 0; k < cols2; k++) { memo[i, j, k] = -1; } } } return memo; } // Main method to initiate calculation public static void Main( string [] args) { int [,] power = { { 2, 4, 6 }, { 8, 0, 10 }, { 6, 3, 9 } }; int rows = power.GetLength(0); int cols = power.GetLength(1); int [,,] memo = InitializeMemo(rows, cols, cols); // Calculate and print the combined minimum power Console.WriteLine( "Combined Minimum Power: " + TotalPower(0, 0, cols - 1, power, rows, cols, memo)); } } |
Javascript
// Function to calculate the combined minimum power function totalPower(i, j1, j2, power, rows, cols, memo) { // Base case: both "+" and "-" reach the last row if (i === rows - 1) { return 0; } // Check if the value is already calculated and stored in memo if (memo[i][j1][j2] !== -1) { return memo[i][j1][j2]; } let mini = Infinity; // At each (i, j), there are 9 combined possibilities // 3 possibilities for j1 (from -1 to 1), and the same for j2 // Thus, a total of 3 * 3 possibilities for (let k = -1; k <= 1; k++) { for (let p = -1; p <= 1; p++) { const nextI = i + 1; const nextJ1 = j1 + k; const nextJ2 = j2 + p; // Check the validity of the path and ensure there is no collision if ( nextI >= 0 && nextI < rows && nextJ1 >= 0 && nextJ1 < cols && nextJ2 >= 0 && nextJ2 < cols && nextJ1 !== nextJ2 ) { const value = Math.abs(power[nextI][nextJ1] - power[i][j1]) + Math.abs(power[nextI][nextJ2] - power[i][j2]); // Recursively call for the next i, j1, and j2 const result = totalPower(nextI, nextJ1, nextJ2, power, rows, cols, memo); // Take the minimum mini = Math.min(mini, value + result); } } } // Store the calculated value in memo memo[i][j1][j2] = mini; // Return the answer return mini; } // Driver code function main() { const power = [[2, 4, 6], [8, 0, 10], [6, 3, 9]]; const rows = power.length; const cols = power[0].length; const memo = new Array(rows).fill( null ).map(() => new Array(3).fill( null ).map(() => new Array(3).fill(-1))); console.log( "Combined Minimum Power: " + totalPower(0, 0, cols - 1, power, rows, cols, memo)); } main(); |
Combined Minimum Power: 10
Complexity Analysis:
- Time Complexity: The time complexity of the given solution is O(N3), where N represents the number of columns in the power matrix. This is because, at each cell (i, j1, j2), we iterate over all possible combinations of j1 and j2.
- Auxiliary Space: The space complexity of the given solution is O(N3) as well. This is because we use a 3D array
memo
to store the calculated values for each state (i, j1, j2), resulting in a space requirement of O(N3).
Contact Us