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;
}
