HackerRank Ones and Twos problem solution YASH PAL, 31 July 2024 In this HackerRank Ones and Twos problem solution, You are using at most A number of 1s and at most B number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * sign are allowed? Topics we are covering Toggle Problem solution in Java.Problem solution in C++.Problem solution in C. Problem solution in Java. 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(); } } } Problem solution in C++. #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("%dn",(an+MOD-1)%MOD); } return 0; } Problem solution in C. #include <stdio.h> #include <stdlib.h> #define MOD 1000000007 long long dp[1001][1001][31]={0},dp3[1001]; int main(){ int T,A,B,l,i,j,k; long long t,f; for(k=0;k<31;k++) for(i=k+1;i<=1000;i++) for(j=k+1;j<=1000;j++) if(i==k+1){ if(j==k+1) dp[i][j][k]=1; } else{ dp[i][j][k]=dp[i-1][j][k]; if(j>i) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-i][k])%MOD; if(i==j) dp[i][j][k]=(dp[i][j][k]+1)%MOD; } scanf("%d",&T); while(T--){ scanf("%d%d",&A,&B); i=A; for(k=0;i;i>>=1,k++); for(i=0,t=1;i<k+1;i++,t<<=1); dp3[0]=(A+1)%MOD; l=1; for(i=f=1,j=2;i<=k && i<=B;i++,j<<=1,l=i) if(j+A<t) dp3[i]=(j+A+1)%MOD; else{ dp3[i]=t%MOD; f=0; l=i+1; break; } if(f){ f=((j>>1)&0x7fffffff); for(i=1,j=2;i<=k-1 && i+k<=B;i++,j<<=1,l=i+k) if(j+f+A<t) dp3[i+k]=(j+f+A+1)%MOD; else{ dp3[i+k]=t%MOD; l=i+k+1; break; } } for(;l<1001;l++) dp3[l]=dp3[l-1]; for(i=k+1,t=dp3[1000];i<=B;i++) t=(t+dp[B][i][k]*dp3[B-i])%MOD; printf("%lldn",(t-1+MOD)%MOD); } return 0; } Algorithms coding problems solutions