The Hackerearth January Easy Challenge

Is there anyone who have already solved this problem?


Ikshu recently learnt to generate random numbers. He is generating stream binary numbers. Uptil now he has generated N bits of the binary number. Now, he wants to know if there is a streak of contiguous 1’s of length K.

Help him to find the probability of existence of such a streak in his binary number.

Assume that probability of generating a one and zero is equal i.e 0.5.

First and only line of input contains two space separated integers N and K as described above.

output contains one line containing probablity. output should be in n/m form where it is n/m is in its lowest fraction.

[1]: Log In | HackerEarth

Since I really encourage you to solve it on your own, I’ll give you a few hints:

Let’s count the number of binary strings of length n which don’t have a substring of k consecutive 1’s. If we can do this, we can obviously solve the problem.

Let dp[n] be the number of binary strings of length n which don’t have a substring of k consecutive 1’s and which has the n-th bit set to 0.

Obviously, the base case, dp[1] = 1 i.e. the empty string.

Then you can compute dp[n + 1] based on values of dp[i] for some i < n. Try to solve it on your own, but if you stuck, I’ll give you a more detailed explanation.

The answer to the problem is dp[n + 1], where n is the length of desired binary string.


You can see my code from the contest here:


I solved this using a formula and managed 12 points only. I am new to dp and any furthur help would be heartfully appreciated.

using namespace std;
int main()
int n,k;
long long int num,dem,y;
int z=n-k+1;
int i;



@leduongtuananh @subham_pasari

This problem can be solved easily using the Digit DP

I solved it and managed to get the 100 points

My Solution

For learning Digit DP, visit Praveen Dhinwa Blog, A nice explanantion is provided there

1 Like

Sure, I solved it, what do you need?

@pkacprzak :slight_smile: Sorry for missing. I need an algorithm to solve it :slight_smile:

I’m not good at dp :frowning: Can you describe it more clearly?

Please check my code for a more detailed explanation (link in the post). I hope that it helps.