# HackerRank Vim War problem solution

In this HackerRank Vim War problem solution, A war has broken down between Vim and Emacs. Gedit, being Vim's ally, is captured by Emacs as a prisoner of war and it is up to Vim to rescue him by defeating Emacs.

For this task, Vim has to assemble an army of appropriate skills. He can choose a non-empty subset of soldiers from a set of N soldiers (numbered from 1 to N). Each soldier has some subset of skills out M of different skills (numbered from 1 to M). The skill-set of an army is the union of skill-sets of its constituent soldiers. To win the war, Vim needs to know how many different subsets of soldiers satisfy his skill-set requirement.

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {
private static PrintWriter out;
public static int mod = 1000000007;
public static int N,M,K,s[];
public static long[] mult;

public static void main(String[] args) throws IOException {
out = new PrintWriter(System.out, true);

N = in.nextInt();
M = in.nextInt();
s = new int[N];
for (int i = 0; i < N; i++) s[i] = Integer.parseInt(in.next(), 2);
int goal = Integer.parseInt(in.next(), 2);
if (goal == 0) {
out.println(0);
out.close();
System.exit(0);
}

int K = Integer.bitCount(goal);
mult = new long[1<<K]; Arrays.fill(mult, 1);
int w = ~goal;
for (int i = 0; i < N; i++) {
if ((w & s[i]) == 0) {
int k = 0, a = 0;
for (int j = 0; j < M; j++) if ((goal & (1 << j)) != 0) a |= ((s[i] >> j) & 1) << (k++);
mult[a] = (mult[a] << 1) % mod;
}
}

long[] m = rec(0, (1<<K)-1);
long res = 0;
for (int i = 0; i < 1 << K; i++) {
long sign = (Integer.bitCount(i) & 1) == (K & 1) ? 1 : (mod-1);
res = (res + sign * m[i]) % mod;
}
out.println(res);
out.close();
System.exit(0);
}

public static long[] rec(int from, int to) {
if (from == to) return new long[] {mult[from]};
int mid = (from+to) >> 1;
long[] a = rec(from, mid);
long[] b = rec(mid+1, to);
long[] ret = new long[to-from+1];
for (int i = 0; i < a.length; i++) {
ret[i] = a[i];
ret[i+a.length] = a[i]*b[i] % mod;
}
return ret;
}

public StringTokenizer tokenizer;

tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}

public int nextInt() {
return Integer.parseInt(next());
}
}

}```

## Problem solution in C++.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int Maxn = 100005;
const int Maxm = 20;
const int mod = 1000000007;

int pw[Maxn];
int n, m;
int has[1 << Maxm];
char str[Maxn][Maxm + 2], need[Maxm + 2];
int res;

int main() {
pw[0] = 1;
for (int i = 1; i < Maxn; i++)
pw[i] = 2 * pw[i - 1] % mod;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%s", str[i]);
scanf("%s", need);
for (int i = 0; i < n; i++) {
bool ok = true;
for (int j = 0; j < m && ok; j++)
ok = str[i][j] == '0' || need[j] == '1';
if (!ok) continue;
int pnt = 0;
for (int j = 0; j < m; j++)
if (need[j] == '1')
mask |= (str[i][j] == '0') << pnt++;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < 1 << m; j++)
if (j & 1 << i) has[j ^ 1 << i] += has[j];
for (int i = 0; i < 1 << m; i++)
if (__builtin_popcount(i) % 2 == 0)
res = (res + pw[has[i]]) % mod;
else res = (res - pw[has[i]] + mod) % mod;
printf("%d\n", res);
return 0;
}```

## Problem solution in C.

```#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX 1048576
#define MOD 1000000007
#define clr(ar) memset(ar, 0, sizeof(ar))

int n, m, r, pos[25], ar[MAX], temp[MAX], P[MAX], dp[MAX][2];

int Solve(){
int i, j, k, x, y, u, v, bitmask;

clr(dp);
for (i = 0; i < n; i++) dp[ar[i]][0]++;

for (j = 1; j < 21; j++){
u = j & 1;
v = (j - 1) & 1;

for (i = 0; i < MAX; i++){
if (i & (1 << (j - 1))) dp[i][u] = dp[i][v];
else dp[i][u] = (dp[i][v] + dp[i + (1 << (j - 1))][v]);
}
}

int res = P[n];
if (x){
if (__builtin_popcount(bitmask) & 1) res = (res - P[x] + MOD) % MOD;
else res = (res + P[x]) % MOD;
}
}

return res;
}

int main(){
char str[25];
int i, j, k, x, lim;

P[0] = 1;
for (i = 1; i < MAX; i++) P[i] = (P[i - 1] << 1) % MOD;
for (i = 0; i < MAX; i++) P[i] = (P[i] - 1 + MOD) % MOD;

while (scanf("%d %d", &n, &m) != EOF){
for (i = 0; i <= n; i++){
x = 0;
scanf("%s", str);

for (j = 0; str[j]; j++) x = (x << 1) + (str[j] - 48);
temp[i] = x;
}

r = n;
n = 0, k = 0;
memset(pos, -1, sizeof(pos));

for (j = 0; j < m; j++){
if (temp[r] & (1 << j)) pos[j] = k++;
}

lim = (1 << k) - 1;
for (i = 0; i < r; i++){
x = 0, k = 0;
for (j = 0; j < m; j++){
if (temp[i] & (1 << j)){
if (pos[j] == -1){
k = 1;
break;
}
x |= (1 << pos[j]);
}
}
if (!k) ar[n++] = x ^ lim;
}

printf("%d\n", Solve());
}
return 0;
}```