Table of Contents
Ones and Twos – 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<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MOD = 1e9 + 7;
int dp_sum[1001][1001],dp_bit[1001][1001];
void add(int &x,long long v){
v%=MOD;
x+=v;
if(x>=MOD)x-=MOD;
}
int f_bit(int lv,int B);
int f_sum(int lv,int B){
if(lv>B)return 1;
if(dp_sum[lv][B]!=-1)return dp_sum[lv][B];
int tmp=f_sum(lv+1,B);
add(tmp,f_bit(lv,B));
return dp_sum[lv][B]=tmp;
}
int f_bit(int lv,int B){
if(lv>B)return 0;
if(dp_bit[lv][B]!=-1)return dp_bit[lv][B];
return dp_bit[lv][B]=f_sum(lv+1,B-lv);
}
int main(){
int T,A,B;
scanf("%d",&T);
memset(dp_sum,-1,sizeof(dp_sum));
memset(dp_bit,-1,sizeof(dp_bit));
while(T--){
scanf("%d%d",&A,&B);
int an=0;
if(A==0)an=f_sum(1,B);
else{
int k=1;
while((1LL<<k)<=A)k++;
k++;
add(an,(long long)(A+1)*f_sum(k,B));
long long ha=(1LL<<k)-A-1;
int now=0,i=1;
long long last=0;
while(ha>0){
now++;
if(B<now)break;
add(an,min((1LL<<i)-last,ha)*f_sum(k,B-now));
ha-=(1LL<<i)-last;
last=1LL<<i;
i++;
if(i==k){
last=0;
i=1;
}
}
/*
long long last=A;
for(int i=1;i<=B;i++){
if(last+1>=(1LL<<k))break;
add(an,(min(((long long)A+(1LL<<i)),(1LL<<k)-1)-last)*f_sum(k,B-i));
last=min((long long)A+(1LL<<i),(1LL<<k)-1);
}*/
}
printf("%d\n",(an+MOD-1)%MOD);
}
return 0;
}
Java rep HackerRank Solution
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Solution {
static Solution main;
public class Range implements Comparable<Range> {
int minPower;
int maxPower;
long range;
public Range(int min , int max , long r) {
minPower = min;
maxPower = max;
range = r;
}
public int compareTo(Range r) {
int comp = new Integer(minPower).compareTo(r.minPower);
if(comp!=0) {
return comp;
}
return new Integer(maxPower).compareTo(r.maxPower);
}
}
public static void main(String[] args) {
main = new Solution();
long [][] dp = new long[1001][1001];
long [][] dp1 = new long[1001][1001];
long [][] dpsum = new long[1001][1001];
long sp = 1000000007;
for(int i = 0 ; i < 1001 ; i++) {
Arrays.fill(dp[i], 0);
}
long [] pow2 = new long [32];
pow2[0] = 1;
for(int i = 1 ; i <32 ; i++) {
pow2[i ] = pow2[i-1] * 2;
}
dp[1][1] = 1;
for(int i = 2 ; i < 1001 ; i++) {
for(int j = 1 ; j <= i ; j++) {
long temp = 0;
for(int k = j+1 ; k < i ; k++) {
temp += dp[i-j][k];
if(temp>=sp) {
temp-=sp;
}
}
if(i==j) {
temp++;
if(temp>=sp) {
temp-=sp;
}
}
dp[i][j] = temp ;
}
}
for(int k = 0 ; k < 1001 ; k++) {
Arrays.fill(dp1[k],0);
}
for(int i = 0 ; i < 1001 ; i++) {
dpsum[i][0] = 0;
}
for(int i = 0 ; i < 1001 ; i++) {
for(int j = 1 ; j < 1001 ; j++) {
dpsum[i][j] = dpsum[i][j-1] + dp[i][j];
if(dpsum[i][j]>=sp) {
dpsum[i][j] -= sp;
}
}
}
for(int k = 1 ; k < 1001 ; k++) {
for(int i = k ; i < 1001 ; i++) {
if(i==k) {
dp1[i][k] = 1;
} else {
dp1[i][k] = dp1[i-1][k] + dp[i][k];
if(dp1[i][k] >= sp) {
dp1[i][k] -= sp;
}
}
}
}
long [][][] list = new long[1001][32][32];
long [] all = new long[1001];
for(int i = 0 ; i < 1001 ; i++) {
for(int j = 0 ; j < 32 ; j++) {
for(int k = 0 ; k < 32 ; k++) {
list[i][j][k] = 0;
}
}
all[i] = 0;
for(int j = 1 ; j <= Math.min(i/2, 500) ; j++) {
for(int k = j + 1 ; k <= i-j ; k++) {
long repValue = 0;
if(j+k==i) {
repValue ++;
}
repValue += dpsum[i-j-k][i-j-k] - dpsum[i-j-k][k];
if(repValue<0) {
repValue += sp;
}
if(repValue>=sp) {
repValue -= sp;
}
if(k<32) {
list[i][j][k] = repValue;
} else {
all[i] += repValue;
}
}
}
all[i] %= sp;
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedOutputStream bos = new BufferedOutputStream(System.out);
String eol = System.getProperty("line.separator");
byte[] eolb = eol.getBytes();
try {
String str = br.readLine();
int t = Integer.parseInt(str);
for(int i = 0 ; i < t ; i++) {
str = br.readLine();
int blank = str.indexOf(" ");
int a = Integer.parseInt(str.substring(0,blank));
int b = Integer.parseInt(str.substring(blank+1));
long ans = 0;
if(b==0) {
bos.write(new Long(a).toString().getBytes());
}else if (a==0){
for(int d = 0 ; d <= b ; d++) {
long temp = dp1[b][d];
ans += temp;
}
ans %= sp;
bos.write(new Long(ans).toString().getBytes());
} else {
for(int d = 0 ; d < b ; d++) {
long temp = dp1[b-1][d];
long mult = 2;
temp *= mult;
ans += temp;
}
ans %= sp;
for(int d = 0 ; d < 32 ; d++) {
for(int e = d+1 ; e < 32 ; e++ ) {
long repValue = list[b][d][e];
long temp = repValue * Math.min(a+1,pow2[e]-pow2[d]);
ans += temp;
ans %= sp;
}
}
ans %= sp;
long temp = all[b] * (a+1);
ans += temp;
ans+=a+2;
ans %= sp;
bos.write(new Long(ans).toString().getBytes());
}
bos.write(eolb);
}
bos.flush();
} catch(IOException ioe) {
ioe.printStackTrace();
}
}
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define LOCAL 0
#define DEBUG 0
#define USE_BRUTE_FORCE 0
#define NMAX 1002
#define MOD 1000000007
#define INF 1000000000
int cnt[NMAX][NMAX], scnt[NMAX][NMAX];
void ComputeCnt() {
int i, j;
for (j = 0; j < NMAX; j++)
cnt[0][j] = 1;
for (i = 1; i < NMAX; i++) {
if (i == NMAX - 1)
cnt[i][NMAX - 1] = 1;
else
cnt[i][NMAX - 1] = 0;
for (j = NMAX - 2; j >= 0; j--) {
cnt[i][j] = cnt[i][j + 1];
if (j > 0 && j <= i)
cnt[i][j] = (cnt[i][j] + cnt[i - j][j + 1]) % MOD;
}
}
for (j = 1; j < NMAX; j++) {
scnt[NMAX - 1][j] = cnt[NMAX - 1][j];
for (i = NMAX - 2; i >= 0; i--)
scnt[i][j] = (scnt[i + 1][j] + cnt[i][j]) % MOD;
}
}
#define sum(X, Y, Z) ((scnt[X][Z] - scnt[Y + 1][Z] + MOD) % MOD)
int A, Amax, B, ans, anstmp, i, j, k, bmax;
#define VMAX 10000
char ok[VMAX], ok2[VMAX];
int sum2, bfans;
void Gen2(int left, int lpow) {
ok2[sum2] = 1;
for (lpow++; lpow <= left; lpow++) {
sum2 += (1 << lpow);
Gen2(left - lpow, lpow);
sum2 -= (1 << lpow);
}
}
void BruteForce() {
memset(ok, 0, sizeof(ok));
memset(ok2, 0, sizeof(ok2));
sum2 = 0;
Gen2(B, 0);
int i, j;
for (i = 0; i < VMAX; i++)
if (ok2[i]) {
for (j = 0; j <= A; j++)
ok[i + j] = 1;
}
bfans = 0;
for (i = 1; i < VMAX; i++) {
bfans += ok[i];
//if (ok[i]) fprintf(stderr, "bfok: %d\n", i);
}
fprintf(stderr, "BFans=%d\n", bfans);
}
unsigned int ls[NMAX], tli[NMAX], tls[NMAX], lii, lsi, xls;
int cost[NMAX], tcost[NMAX], nint, ntint, c, p;
int InsertInterval(int poz, unsigned int lsi, int c) {
if (poz > 1 && cost[poz - 1] == c) {
ls[poz - 1] = lsi;
return poz - 1;
}
//if (poz <= nint && cost[poz] == c)
// return poz;
for (int k = nint + 1; k >= poz; k--) {
ls[k] = ls[k - 1];
cost[k] = cost[k - 1];
}
ls[poz] = lsi;
cost[poz] = c;
nint++;
return poz;
}
void MergeIntervals() {
int k;
ntint = 1;
for (k = 2; k <= nint; k++)
if (cost[k] == cost[ntint])
ls[ntint] = ls[k];
else {
ntint++;
ls[ntint] = ls[k];
cost[ntint] = cost[k];
}
nint = ntint;
}
int main() {
int tstart = clock();
//freopen("x.txt", "r", stdin);
ComputeCnt();
int T;
if (LOCAL)
T = 50000;
else
scanf("%d", &T);
while (T--) {
if (LOCAL) {
A = 1000000000; B = 1000;
} else
scanf("%d %d", &A, &B);
if (USE_BRUTE_FORCE)
BruteForce();
if (B == 0)
printf("%d\n", A);
else if (A == 0)
printf("%d\n", sum(1, B, 1));
else if (A == 1)
printf("%d\n", (sum(1, B, 1) + sum(0, B, 1)) % MOD);
else {
for (bmax = 29; bmax >= 0; bmax--)
if (A & (1 << bmax))
break;
bmax++;
if (DEBUG)
fprintf(stderr, "A=%d B=%d bmax=%d\n", A, B, bmax);
nint = 2;
ls[0] = (unsigned int) (-1);
ls[1] = A; cost[1] = 0;
ls[2] = (1U << (bmax + 1)) - 1; cost[2] = INF;
for (c = bmax; c >= 1; c--) {
if (DEBUG)
fprintf(stderr, " c=%d: nint=%d\n", c, nint);
ntint = 0;
for (i = 1; i <= nint; i++) {
if (cost[i] == INF) continue;
ntint++;
tli[ntint] = ls[i - 1] + 1 + (1U << c);
tls[ntint] = ls[i] + (1U << c);
tcost[ntint] = cost[i] + c;
if (tcost[ntint] >= 2 * bmax || tcost[ntint] > B)
ntint--;
}
for (i = j = 1; i <= ntint && j <= nint; i++)
for (; j <= nint; j++) {
if (ls[j - 1] + 1 > tls[i]) break;
if (ls[j] < tli[i]) continue;
if (cost[j] <= tcost[i]) continue;
lii = tli[i];
if (ls[j - 1] + 1 > lii) lii = ls[j - 1] + 1;
lsi = tls[i];
if (ls[j] < lsi) lsi = ls[j];
if (lii <= lsi) {
if (lii == ls[j - 1] + 1 && lsi == ls[j]) {
cost[j] = tcost[i];
} else if (lii == ls[j - 1] + 1 && lsi < ls[j]) {
if (InsertInterval(j, lsi, tcost[i]) < j)
j--;
} else if (lii > ls[j - 1] + 1 && lsi == ls[j]) {
ls[j] = lii - 1;
InsertInterval(j + 1, lsi, tcost[i]);
} else {
xls = ls[j];
ls[j] = lii - 1;
p = InsertInterval(j + 1, lsi, tcost[i]);
InsertInterval(p + 1, xls, cost[j]);
}
}
}
MergeIntervals();
}
ans = 0;
for (i = 1; i <= nint; i++) {
if (cost[i] > B) continue;
anstmp = ((long long) (ls[i] - ls[i - 1]) * (long long) sum(0, B - cost[i], bmax + 1)) % MOD;
if (DEBUG)
fprintf(stderr, "interval %d: [%u-%u] cost=%d: anstmp=%d\n", i, ls[i - 1] + 1, ls[i], cost[i], anstmp);
ans += anstmp;
if (ans >= MOD) ans -= MOD;
}
ans = (ans + MOD - 1) % MOD;
if (!LOCAL)
printf("%d\n", ans);
if (USE_BRUTE_FORCE && ans != bfans)
exit(1);
}
}
fprintf(stderr, "Duration=%.3lf sec\n", (double) (clock() - tstart) / CLOCKS_PER_SEC);
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
