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

# Need help with this hourrank-2 question !!

**va1ts7_100**#2

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
```

“);

}

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

",sum);

}

return 0;

}

happy coding

**shiva_google**#3

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**#4

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

**va1ts7_100**#5

@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 !