In this HackerRank Minimum operation 4 problem solution, the task is to debug the existing code to successfully execute all provided test files.
There are n boxes in front of you. For each i, box i contains r[i] red balls, g[i] green balls, and b[i] blue balls.
You want to separate the balls by their color. In each operation, you can pick a single ball from some box and put it into another box. The balls are separated if no box contains balls of more than one color.
Debug the given function min_operations and compute the minimal number of operations required to separate the balls.
Problem solution in Python.
def min_operations(red, green, blue): dp = [[(1<<30) for x in range(8)] for y in range(101)] n = len(red) dp[0][0] = 0 for i in xrange(0, n): for j in xrange(0, 8): dp[i + 1][j | 1] = min(dp[i + 1][j | 1], dp[i][j] + green[i] + blue[i]) dp[i + 1][j | 2] = min(dp[i + 1][j | 2], dp[i][j] + red[i] + blue[i]) dp[i + 1][j | 4] = min(dp[i + 1][j | 4], dp[i][j] + red[i] + green[i]) j = 0 for i in range(0, n): if red[i]: j |= 1 if green[i]: j |= 2 if blue[i]: j |= 4 if dp[n][j] >= (1<<30): dp[n][j] = -1 return dp[n][j] n = int(input()) red = [] green = [] blue = [] for i in range(n): r, g, b = map(int, input().split()) red.append(r) green.append(g) blue.append(b) print(min_operations(red, green, blue))
Problem solution in Java.
import java.util.*; class MinimumOperations { private static final Scanner scan = new Scanner(System.in); int n, r ,g, b; int[][] dp = new int[110][1<<3]; Vector<Integer> red = new Vector(); Vector<Integer> green = new Vector(); Vector<Integer> blue = new Vector(); public void get() { n = scan.nextInt(); for (int i = 0; i < n; i++) { r = scan.nextInt(); g = scan.nextInt(); b = scan.nextInt(); red.add(r); green.add(g); blue.add(b); } } public void minOperations() { int i, j; for (i = 0; i <= n; i++) { for (j = 0; j <= 7; j++) { dp[i][j] = (1<<30); } } dp[0][0] = 0; for (i = 0; i < n; i++){ for (j = 0; j <= 7; j++){ dp[i + 1][j | 1] = Math.min(dp[i + 1][j | 1], dp[i][j] + green.get(i) + blue.get(i)); dp[i + 1][j | 2] = Math.min(dp[i + 1][j | 2], dp[i][j] + red.get(i) + blue.get(i)); dp[i + 1][j | 4] = Math.min(dp[i + 1][j | 4], dp[i][j] + red.get(i) + green.get(i)); } } j = 0; for (i = 0; i < n; i++){ if (green.get(i) != 0) j |= 1; if (red.get(i) != 0) j |= 2; if (blue.get(i) != 0) j |= 4; } if (dp[n][j] >= (1<<30)) dp[n][j] = -1; System.out.println(dp[n][j]); } } class Solution { public static void main(String[] args) { MinimumOperations obj = new MinimumOperations(); obj.get(); obj.minOperations(); } }
Problem solution in C++.
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <vector> #include <cmath> #include <iostream> #include <map> using namespace std; int dp[110][1<<3]; int min_operations(vector <int> red, vector <int> green, vector <int> blue) { int n = (int)red.size(), i, j; for (i = 0; i < 110; i++) { for (j = 0; j < 8; j++) { dp[i][j] = 1<<30; } } dp[0][0] = 0; for (i = 0; i < n; i++){ for (j = 0; j < 8; j++){ dp[i + 1][j | 1] = min(dp[i + 1][j | 1], dp[i][j] + green[i] + blue[i]); dp[i + 1][j | 2] = min(dp[i + 1][j | 2], dp[i][j] + red[i] + blue[i]); dp[i + 1][j | 4] = min(dp[i + 1][j | 4], dp[i][j] + red[i] + green[i]); } } j = 0; for (i = 0; i < n; i++){ if (red[i]) j |= 1; if (green[i]) j |= 2; if (blue[i]) j |= 4; } if (dp[n][j] >= (1<<30)) dp[n][j] = -1; return dp[n][j]; } int main() { int n, r, g, b; cin >> n; vector<int> red, blue, green; for(int i = 0; i < n; i++){ cin >> r >> g >> b; red.push_back(r); green.push_back(g); blue.push_back(b); } cout << min_operations(red, green, blue) << "n"; return 0; }