https://www.hackerrank.com/contests/hourrank-2/challenges/gugas-function . I read the editorial but it was very terrible. How to solve this?

Hello @ AnoopNarang

```
consider you are 5 digits(n=5)
now you can place 10001 only in one way.
1*1=1
you can place 1001 in two ways
_ 1001
1001 _
here each way will give two possible ans.
2*2=4
Similarly you can place 101 in 3 ways
101 _ _
_ 101 _
_ _ 101
here each way will give 4 possible ans.
4*3=12
total ans= 12 + 4 + 1=17
If you notice for other higher didgits too . you will get a general formula
total ans =summation of ( pow(2,i-1)*i ) , where i will vary from 1 to n-2.
```

here is my code for the same problem

```
#include<stdio.h>
# define M 1000000009
int main()
{
int n,i;
long long int sum=1;
long long int temp=1;
scanf("%d",&n);
if(n==3)
{
printf("1\n");
}
else
{
for(i=2;i<=n-2;i++)
{ temp=temp*2;
if(temp>=M)
{
temp=temp%M;
}
sum = sum + (temp*i) ;
if(sum>M)
sum=sum%M;
}
printf("%lld\n",sum);
}
return 0;
}
```

happy coding

I checked your answer, its getting accepted. But i did not get

```
Similarly you can place 101 in 3 ways
101 _ _ _ _
_ _ 101 _ _
_ _ _ _ 101
here each way will give 4 possible ans.
4*3=12
Wont there be repetitions in these 12 combinations. Like
101 _ _ _ _ -------- 101[01]
_ _ _ _ 101 -------- [10]101
```

Since the contest is of 1 hour, just try to do the problem in another way also(shortcut) as follows.

f(1) = 0

f(2) = 1

f(3) = 5

f(4) = 17

So, now that u have got some numbers check for the common formula/pattern in [OEIS(CLICK HERE FOR SOLUTION)]

1

So, the formula is (n-1)*2^n + 1.

so, in this way, u can get AC in 5-8 minutes max. but the most important thing is that u must definitely read and understand the editorial after the contest.

PS:- Even i also did not get this question accepted becoz i took n^2 instead of 2^n and messed up everything. Also,even i did not understand editorial properly.

@Anoopnarang, you can draw this on paper for 5 digits. then you will understand better why there will not be repetition . Bcoz when i was solving this question , i was confused too like you , and i solved it by drawing cases on paper…!

Short exlanation-:

in number 10101, there will be two contributions to the ans , starting (101) and ending (101) , and my approach counted it twice too so , no repititions !

Ok got it … thanks for the efforts man !!

anytime bro