# 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];
}
}
}
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--) {
}
}
if (s[k]) {
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;
}```