Help me solve this question asked in my interview

general
1

There are A children in a town and Santa bought A gifts for them. But he came to know about all the pairs of which gift made which children happy. There were some gifts which made some children super happy. Santa also knew about this. Santa wanted to know among all the combinations of gifting these A gifts to A children which combinations made all A children happy or made at least one child super happy.

Given a 2D integer array B of size A*A where

B[i][j] = 1 if the jth gift does not make the ith child happy.

B[i][j] = 2 if the jth gift makes the ith child happy. B[i][j]=3 if the jth gift makes the ith child super happy.

Problem Constraints

1 <= A <= 13

Input Format

The first argument is a single integer A. The second argument is a 2D integer array B.

Output Format

Return a single integer that is among all the combinations of gifting these A gifts to A children which combinations made all A children happy or made at least one child super happy.

Example Input

Input 1

A * 2

-[[2, 2],

[2, 1] ]

Input 2:

A= 3

  • [[1, 1, 3] ,[2, 2, 3], [1, 3, 3 ]]

Example Output

Output 1:-
1
Output 2:
6
Example Explanation

Explanation 1:-

Only possible combination of gifting is [2, 1]

Explanation 2:-

The possible combinations of gifting are [3, 1, 2], [3, 2, 1], [1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1)

give an approach to solve this problem

2

To solve this problem in C++, you can use dynamic programming to find the maximum number of children that can be made happy by selecting the appropriate gifts. Here’s a C++ code snippet to achieve this:
include <bits/stdc++.h>
using namespace std;

int maxHappyChildren(int A, vector<vector> &B) {
vector<vector> dp(1 << A, vector(A, 0));

for (int mask = 0; mask < (1 << A); ++mask) {
    for (int child = 0; child < A; ++child) {
        if (child == 0) {
            for (int gift = 0; gift < A; ++gift) {
                if (!(mask & (1 << gift))) {
                    dp[mask][child] = max(dp[mask][child], B[child][gift]);
                }
            }
        } else {
            for (int gift = 0; gift < A; ++gift) {
                if (!(mask & (1 << gift))) {
                    dp[mask][child] = max(dp[mask][child], B[child][gift] + dp[mask | (1 << gift)][child - 1]);
                }
            }
        }
    }
}

int maxHappiness = 0;
for (int mask = 0; mask < (1 << A); ++mask) {
    if (dp[mask][A - 1] >= 2) {
        maxHappiness = max(maxHappiness, __builtin_popcount(mask));
    }
}

return maxHappiness;

}

int main() {
int A;
cin >> A;
vector<vector> B(A, vector(A));
for (int i = 0; i < A; ++i) {
for (int j = 0; j < A; ++j) {
cin >> B[i][j];
}
}

int result = maxHappyChildren(A, B);
cout << result << endl;

return 0;

}

1 Like
3

is it working