Need help with this hourrank-2 question !!

hackerrank

#1

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


#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=temp2;
if(temp>=M)
{
temp=temp%M;
}
sum = sum + (temp
i) ;
if(sum>M)
sum=sum%M;
}
printf(”%lld
",sum);
}
return 0;
}

happy coding


#3

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


#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


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


#6

Ok got it … thanks for the efforts man !!


#7

anytime bro :slight_smile: