Table of Contents
Tastes Like Winning – 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 <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef long double ld;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
const int mod = 1000000007;
ll mpow(ll x, ll n) {
ll res = 1;
while (n) {
if (n & 1) res = res * x % mod;
x = x * x % mod;
n /= 2;
}
return res;
}
int stupid(int n, int m) {
int c = 0;
int all = (1 << m) - 1;
for (int mask = 1; mask < (1 << all); ++mask) if (__builtin_popcount(mask) == n) {
int xr = 0;
for (int i = 0; i < all; ++i) if (mask & (1 << i)) {
xr ^= 1 + i;
}
if (xr) ++c;
}
for (int i = 2; i <= n; ++i) c = c * (ll)i % mod;
return c;
}
int solve(int n, int m) {
vi d(n + 1);
vi a(n + 1);
d[0] = 1;
d[1] = 0;
ll dif = mpow(2, m) - 1;
a[0] = 1;
for (int i = 1; i <= n; ++i) a[i] = a[i-1] * (dif - i + 1) % mod;
for (int i = 2; i <= n; ++i) {
d[i] = (a[i-1] - d[i-2] * (dif - i + 2) % mod * (i-1) - d[i-1]) % mod;
//cerr << i << ' ' << d[i] << endl;
}
return (a[n] - (ll)d[n] + 2*mod) % mod;
}
int main() {
int n,m;
cin >> n >> m;
cout << solve(n, m) << endl;
//cerr << stupid(n,m) << ' ' << a[n] << 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 G {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni(), m = ni();
// C(2^n, m)
if(m < 33 && n > (1L<<m)-1){
out.println(0);
return;
}
int mod = 1000000007;
long ret = C(pow(2, m, mod)-1, n, mod);
long del = 0;
long num = 1;
long N = pow(2, m-1, mod);
for(int i = 0;i <= n/2;i++){
del += num;
num = num * (N-i) % mod * invl(i+1, mod) % mod * (-1);
}
if(n % 2 == 1)del = -del;
del %= mod;
// x+del+x*(2^m-1) = ret
long x = (ret-del)*invl(pow(2, m, mod), mod) %mod* (pow(2, m, mod)-1)%mod;
if(x < 0)x += mod;
for(int i = 1;i <= n;i++)x = x * i % mod;
out.println(x);
}
public static long C(long n, long r, int p)
{
if(n < 0 || r < 0 || r > n)return 0L;
if(r == 0 || n == r)return 1;
long pe = 0;
for(long i = n/p;i >= 1;i/=p)pe += i;
for(long i = r/p;i >= 1;i/=p)pe -= i;
for(long i = (n-r)/p;i >= 1;i/=p)pe -= i;
if(pe > 0)return 0L;
long flip = n/p-r/p-(n-r)/p;
int nmp = (int)(n%p), rmp = (int)(r%p);
if(nmp < rmp)return 0L;
long ret = C(n/p, r/p, p);
long den = 1;
for(int i = 1;i <= rmp;i++){
ret = ret * (nmp-i+1) % p;
den = den * i % p;
}
ret = ret * invl(den, p) % p;
if(flip % 2 != 0){
ret = -ret;
if(ret < 0)ret += p;
}
return ret;
}
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;
}
public static long pow(long a, long n, long mod) {
// a %= mod;
long ret = 1;
int x = 63 - Long.numberOfLeadingZeros(n);
for (; x >= 0; x--) {
ret = ret * ret % mod;
if (n << 63 - x < 0)
ret = ret * a % mod;
}
return ret;
}
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 G().run(); }
private byte[] inbuf = new byte[1024];
public 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
_=input().split()
mod=10**9+7
n=int(_[0])
m=int(_[1])
M = pow(2, m, mod) - 1
comb_n_1 = (M%mod)* ((M-1)%mod)
nim_n_2 = 0 #total number combinations that is nim for n-2 stacks
nim_n_1 = 0 #total number combinations that is nim for n-1 stacks
nim_n = 0 #total number combinations that is nim for n stacks
if n==1:
print (M%mod)
elif n==2:
print (((M%mod)*((M-1)%mod))%mod)
else:
for i in range(3, n + 1):
nim_n = (comb_n_1 - nim_n_1 - nim_n_2 * (M-i+2) * (i-1)) % mod
'''total number of nim for n stacks = maximum possible number of nim = m!/(m-n+1)!
[n-1 different numbers]
-(n-1 of them is nim)
[nim for n-1 stacks]
-(n-2 of them is nim plus any numbers that is not included)
[nim for n-2 stacks * m-n+2 * n-1]
'''
comb_n_1 = (comb_n_1 * (M - i + 1)) % mod
nim_n_2 = nim_n_1
nim_n_1 = nim_n
print ((comb_n_1 - nim_n) % mod)
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys
n,m = map(int,sys.stdin.readline().split())
p = 1000000007
def pow_mod(x, y, z):
number = 1
while y:
if y & 1:
number = number * x % z
y >>= 1
x = x * x % z
return number
S = pow_mod(2,m,p)-1 % p
A1 = 0
A2 = 0
A3 = S
W = S
z1 = pow_mod(2,m,p)
x = z1-1
for i in range(2,n+1):
x -= 1
A3 = (i * (S-W) * x)%p
S = (S*x)%p
W = (S-A1)
A1 = (W - A3)
#A2 = (S-W)
print W%p
C rep HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
// for xor of n distinct numbers chosen from [1,(2^m -1)], how many are nonzero?
// Well, choose n-1 distinct numbers that don't xor to 0. Multiply by (2^m -1 - (n-1) - 1)'
// oops, above doesn't work because sometimes the n-1 numbers include the one which cancels.
// Okay, so when does it include the one that cancels? When it's a subset of n-2 numbers which
// do xor to 0, added to any other.
//
// Or, choose n-1 distinct numbers which DO xor to 0. Multiply by (2^m - 1 - (n-1))
// How many ways to choose n distinct numbers from [1, 2^m - 1]? C(2^m-1, n) of course
//
// So, how many are zero?
// Choose n-1 distinct numbers which don't xor to 0
// Except those n-1 which consist of n-2 which do add to zero plus one more. Then one will cancel it.
// (note: order matters in the problem)
typedef int num_t;
num_t modulus = 1000000007;
int modmul(int a, int b, int m) {
return ((long)a*b) % m;
}
int modexp(int a, int b, int m) {
if (b == 0) return 1;
if (b&1) {
return ((long)a * modexp(a, b - 1, m)) % m;
}
int r1 = modexp(a, b/2, m);
return ((long)r1*r1) % m;
}
num_t count_nz_xor1(int n, int m, num_t m2m1);
num_t memo0[10000002];
num_t count_z_xor1(int n, int m, num_t m2m1) {
if (n == 0) return 1;
if (n == 1) return 0;
if (memo0[n]) return memo0[n] - 1;
num_t recurse2 = count_z_xor1(n-2, m, m2m1);
recurse2 = modmul(recurse2, n-1, modulus);
num_t recurse1 = count_nz_xor1(n-1, m, m2m1);
num_t mult = m2m1 - (n-2);
if (mult < 0) mult += modulus;
num_t result = recurse1 - modmul(recurse2, mult, modulus);
if (result < 0) result += modulus;
memo0[n] = result + 1;
// fprintf(stderr, "count_z_xor %d %d = %lld\n", n, m, result);
return result;
}
num_t memo[10000002];
num_t count_nz_xor1(int n, int m, num_t m2m1) {
if (n == 0) return 0;
if (n == 1) {
return m2m1;
}
if (memo[n]) return memo[n] -1;
num_t recurse2 = count_z_xor1(n-2, m, m2m1);
num_t recurse1z = count_z_xor1(n-1, m, m2m1);
num_t recurse1n = count_nz_xor1(n-1, m, m2m1);
// num_t xxx = recurse1n - recurse2 * (m2m1 - (n - 2)); // which is exactly count_z_xor(n, m)
num_t xxx = count_z_xor1(n, m, m2m1);
// num_t result = recurse1z * (m2m1 - (n-1)) + xxx * (m2m1 - (n-1) - 1) + (recurse1n - xxx) * (m2m1 - (n-1));
num_t tot = recurse1z + recurse1n;
if (tot >= modulus) tot -= modulus;
num_t mult = m2m1 - (n - 1);
if (mult < 0) mult += modulus;
num_t result = modmul(tot, mult, modulus);
result -= xxx;
if (result < 0) result += modulus;
// num_t result = (recurse1z + recurse1n) * (m2m1 - (n-1)) - xxx;
// note recurse1z + recurse1n = (n-1)! So this amounts to all possibilities for n-1, times all available numbers, minus the number of zeros at this n, which is of course correct.
// fprintf(stderr, "count_nz_xor %d %d = %lld\n", n, m, result);
memo[n] = result + 1;
return result;
}
num_t count_nz_xor(int n, int m) {
num_t m2m1 = modexp(2, m, modulus);
m2m1 -= 1;
if (m2m1 < 0) m2m1 += modulus;
for (int i = 2; i < n; i++) {
count_nz_xor1(i, m, m2m1);
}
return count_nz_xor1(n, m, m2m1);
}
int main() {
int n, m;
scanf("%d %d\n", &n, &m);
// there's one failure where m = 4
if (m > 4) {
// exit(-1);
}
printf("%d", count_nz_xor(n, m));
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
