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 InputReader in;
  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 {
    in = new InputReader(System.in);
    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;
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

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

    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;
        int mask = 0;
        for (int j = 0; j < m; j++)
            if (need[j] == '1')
                mask |= (str[i][j] == '0') << pnt++;
        has[mask]++;
    }
    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("%dn", 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))
#define read() freopen("lol.txt", "r", stdin)

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];
    for (bitmask = 1; bitmask < MAX; bitmask++){
        x = dp[bitmask][0];
        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("%dn", Solve());
    }
    return 0;
}