Need help with this hourrank-2 question !!

Guga's Function | HackerRank . 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

1 Like

@AnoopNarang

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.

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


@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 :slight_smile: