Table of Contents
Counting the Ways – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <sstream>
#include <iostream>
#include <functional>
using namespace std;
#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define forit(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
#define pb push_back
#define mp make_pair
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef vector <int> vi;
typedef pair <int, int> pii;
int a[11]; // weights
int N;
int prod;
int DP[11][100001*11]; // DP[k][n] is number of ways with k weights of achieving total <= n
#define MOD 1000000007
ll mul_inv(ll a, ll b)
{
ll b0 = b, t, q;
ll x0 = 0, x1 = 1;
if (b == 1) return 1;
while (a > 1) {
q = a / b;
t = b, b = a % b, a = t;
t = x0, x0 = x1 - q * x0, x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
// Count ways of combining weights to make target of top
ll f(ll top) {
ll total = 0;
int b = top % prod;
ll top2 = top / prod;
// denumerant evaluated at position a.x+b is polynomial of degree at most 10
// so evaluate at 11 points
int last = 10*prod+b; // last location to evaluate
forn(i,last+1)
DP[0][i] = 1; // Consider weight 0 to be of value 1
for(int k=1;k<=N;k++) {
int w=a[k-1];
forn(i,last+1) {
DP[k][i] = (i>=w) ? ((DP[k][i-w] + DP[k-1][i]) % MOD) : DP[k-1][i];
}
}
forn(x,11) {
ll y = DP[N][x*prod+b];
ll den = 1;
forn(i,11) {
if (i==x) continue;
y = y*(((top2-i)+MOD)%MOD)%MOD;
den = den*(((x-i)+MOD)%MOD)%MOD;
}
total = (total + y*mul_inv(den,MOD)%MOD) % MOD;
}
return total;
}
int main(int argc,char *argv[])
{
ll total = 0;
ll L,R;
cin >> N;
prod = 1;
forn(n,N) {
int x,y;
cin >> a[n];
prod *= a[n];
}
cin >> L >> R;
total = (f(R) - f(L-1) + MOD) % MOD;
cout << total << endl;
return 0;
}
Java rep HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class F {
InputStream is;
PrintWriter out;
String INPUT = "";
int mod = 1000000007;
void solve()
{
int n = ni();
int[] a = na(n);
long L = nl(), R = nl();
int Z = 1200000;
long[] dp = new long[Z+1];
Arrays.fill(dp, 1);
long pe = 1;
for(int v : a){
pe *= v;
for(int i = 0;i+v <= Z;i++){
dp[i+v] += dp[i];
if(dp[i+v] >= mod)dp[i+v] -= mod;
}
}
int[][] fif = enumFIF(30, mod);
long ret = 0;
{
long[] y = new long[12];
for(int i = 0;i < 12;i++){
y[i] = dp[(int)(R%pe+i*pe)];
}
ret += guessDirectly(mod, R/pe, fif, y);
}
{
long[] y = new long[12];
for(int i = 0;i < 12;i++){
y[i] = dp[(int)((L-1)%pe+i*pe)];
}
ret -= guessDirectly(mod, (L-1)/pe, fif, y);
}
if(ret < 0)ret += mod;
out.println(ret);
}
public static int[][] enumFIF(int n, int mod) {
int[] f = new int[n + 1];
int[] invf = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = (int) ((long) f[i - 1] * i % mod);
}
long a = f[n];
long b = mod;
long p = 1, q = 0;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
invf[n] = (int) (p < 0 ? p + mod : p);
for (int i = n - 1; i >= 0; i--) {
invf[i] = (int) ((long) invf[i + 1] * (i + 1) % mod);
}
return new int[][] { f, invf };
}
public static long guessDirectly(long mod, long x, int[][] fif, long... y)
{
int n = y.length;
if(0 <= x && x < n){
return y[(int)x];
}else if(x % mod - (n-1) <= 0){
long mul = 1;
for(int i = 0;i < n;i++){
if((x-i)%mod == 0)continue;
mul = mul * ((x-i)%mod) % mod;
}
long s = 0;
long sig = 1;
long big = 8L*mod*mod;
for(int i = n-1;i >= 0;i--){
if((x-i)%mod == 0){
s += fif[1][i] % mod * fif[1][n-1-i] % mod * y[i] * sig;
if(s >= big)s -= big;
if(s <= -big)s += big;
}
sig = -sig;
}
s %= mod;
if(s < 0)s += mod;
s = s * mul % mod;
return s;
}else{
long mul = 1;
for(int i = 0;i < n;i++){
mul = mul * ((x-i)%mod)%mod;
}
long s = 0;
long sig = 1;
long big = 8L*mod*mod;
for(int i = n-1;i >= 0;i--){
s += invl(x-i, mod) * fif[1][i] % mod * fif[1][n-1-i] % mod * y[i] * sig;
if(s >= big)s -= big;
if(s <= -big)s += big;
sig = -sig;
}
s %= mod;
if(s < 0)s += mod;
s = s * mul % mod;
return s;
}
}
public static long invl(long a, long mod) {
long b = mod;
long p = 1, q = 0;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
return p < 0 ? p + mod : p;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new F().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 rep HackerRank Solution
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)
Python 2 rep HackerRank Solution
C rep HackerRank Solution
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
