×

# Need help with this hourrank-2 question !!

 0 1 https://www.hackerrank.com/contests/hourrank-2/challenges/gugas-function . I read the editorial but it was very terrible. How to solve this? asked 04 Nov '15, 00:44 18●3 accept rate: 0%

 1 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 # 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 answered 04 Nov '15, 15:16 472●1●7●32 accept rate: 11% 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  (04 Nov '15, 20:19) @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 ! (05 Nov '15, 01:50) Ok got it ... thanks for the efforts man !! (05 Nov '15, 11:16) anytime bro :) (05 Nov '15, 11:40)
 0 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) 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. answered 04 Nov '15, 20:38 97●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×310

question asked: 04 Nov '15, 00:44

question was seen: 2,048 times

last updated: 05 Nov '15, 11:40