HackerRank Counting the Ways problem solution

In this HackerRank Counting, the Ways problem solution Little Walter likes playing with his toy scales. He has N types of weights. The Ith weight type has weight Ai. There are infinitely many weights of each type.

Recently, Walter defined a function, F(X), denoting the number of different ways to combine several weights so their total weight is equal to X. Ways are considered to be different if there is a type that has a different number of weights used in these two ways.

Problem solution in Python.

MOD = 10**9 + 7

def lcm(lst):
    ans = 1
    for x in lst:
        ans = ans*x//gcd(ans, x)
    return ans

def gcd(a,b):
    if a<b:
        a, b = b, a
    while b > 0:
        a, b = b, a%b
    return a

def getsoltable(a, m, MOD=MOD):
    soltable = [1] + [0] * (len(a)*m-1)
    for x in a:
        oldsoltable = soltable
        soltable = list(soltable)
        for i in range(x, len(soltable)):
            soltable[i] = (oldsoltable[i] + soltable[i - x]) % MOD
    return soltable

def countsols(const, soltable, lcm):
    offset = const % lcm
    pts = soltable[offset::lcm]
    assert len(pts) == len(a)
    coef = polycoef(pts)
    return polyval(coef, const//lcm)

def polycoef(pts):
    coef = []
    for x, y in enumerate(pts):
        fact = descpower = 1
        for i, c in enumerate(coef):
            y -= descpower*c//fact
            descpower *= x - i
            fact *= i + 1
        coef.append(y)
    return coef
        
def polyval(coef, x):
    ans = 0
    fact = descpower = 1
    for i, c in enumerate(coef):
        ans += c * descpower * pow(fact, MOD-2, MOD)
        descpower = descpower * (x - i) % MOD
        fact *= i + 1
    return ans % MOD
        
n = int(input())
a = [1] + [int(fld) for fld in input().strip().split()]
L, R = [int(fld ) for fld in input().strip().split()]
m = lcm(a)
soltable = getsoltable(a, m)
print((countsols(R, soltable, m) - countsols(L-1, soltable, m)) % MOD)

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    static int MOD = 1000000007;
    
    static int N;
    static int[] arr;
    static List<Integer> listS;
    static int[] pSum;
    static int[] frec;
    static int sizePS;
    static int maxS = 100010;
    static int[][] memo = new int[60][maxS];
    
    static void init() {
        listS = new ArrayList<Integer>();
        for (int s = 1; s < (1 << N); s++){ 
            int x = 0;
            for (int t = 0; t < N; t++) {
                if ((s & (1 << t)) > 0) {
                    x += arr[t];
                }
            }
            listS.add(x);            
        }
        Collections.sort(listS);
        sizePS = listS.size();
        pSum = new int[sizePS];
        frec = new int[sizePS];
        int last = listS.get(0);
        pSum[0] = last;
        frec[0] = 1;
        int index = 0;
        for(int k = 1;k < sizePS;k++) {
            int next = listS.get(k);
            if(next == last) {
                frec[index]++;
            } else {
                last = next;
                pSum[++index] = next;
                frec[index] = 1;
            }
        }
        sizePS = index+1;
    }

    static int countWays(long l, long r) {
        init();
        int aR = recCalc(r, 0);
        memo = new int[60][maxS];
        return (aR + MOD - recCalc(l-1, 0)) % MOD; 
    }

    private static int recCalc(long l, int pos) {
        if(l == 0) {
            return 0;
        }
        int ans = 0;
        if((ans = memo[pos][(int) (l%maxS)]) >= 1) {
            return ans-1;
        }
        
        ans = recCalc(l/2, pos+1);
        for(int k = 0;k < sizePS;k++) {
            int a = pSum[k];
            if(l >= a) {
                int pa = 1+recCalc((l-a)/2, pos+1);
                ans = (int) ((ans + (long)frec[k] * pa) % MOD);
            }else {
                break;
            }
        }
        memo[pos][(int) (l%maxS)] = ans+1;
        return ans;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
        N = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
        arr = new int[N];
        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
        for (int arrItr = 0; arrItr < N; arrItr++) {
            int arrItem = Integer.parseInt(arrItems[arrItr]);
            arr[arrItr] = arrItem;
        }
        String[] lr = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
        long l = Long.parseLong(lr[0]);
        long r = Long.parseLong(lr[1]);
        int result = countWays(l, r);
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
        bufferedWriter.close();
        scanner.close();
    }
}

Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int n;
int a[10];
long long L, R;

const int N = 202000;
int dp0[N];
int dp1[N];

inline void add(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

long long solve(long long v) {
    bitset<62> s(v);
    memset(dp0, 0, sizeof(dp0));
    dp0[0] = 1;

    for (int k = 0; k < 62; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = N - a[i] - 1; j >= 0; j--) {
                add(dp0[j + a[i]], dp0[j]);
            }
        }
        if (s[k]) {
            add(dp0[0], dp0[1]);
            for (int i = 1; i < N - 1; i++) {
                dp0[i] = dp0[i + 1];
            }
        }
        memset(dp1, 0, sizeof(dp1));
        for (int i = 0; i < N; i++) {
            add(dp1[(i + 1) / 2], dp0[i]); 
        }
        swap(dp0, dp1);
    }

    return dp0[0];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> L >> R;

    int ans = solve(R) - solve(L - 1);
    if (ans < 0) ans += MOD;
    cout << ans << endl;
}