Discussion on Sherlock and Square Challenge

8 years ago+ 1 comment

Is there any problem with the logic?

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std; 

int main(){
    int t; 
    cin>>t;
    for(int i=0;i<t;i++){
        long n; 
        cin>>n;
        cout<<2*fmod(1+pow(2,n),MOD)<<"\n";
    }
    return 0;
}

5 years ago+ 0 comments

I'm not sure why you're adding one to your power and multiplying by two. Ignore the outside lines, and it's easy to see that we have 0 lines at n=0, 2 at n=1, 4 at n=2, etc. Further, we can visualise that each new row and each new column will be split at each second, so if we have m lines at n=t, then we will have m+2m lines at n=t+1 (all lines are length 1 of course), written in summation form, we can see that:

4 + {∑(i=1,n) 2^i} will yield the answer (we'll have to check the 0 case later), so let's look at that summation.

I claim that ∑(i=1,n) 2^i = 2^(n+1) - 2

Base case, n=1: 2^(1+1) - 2 = 4-2 = 2 = 2^1

Inductive case: Hypothesis ∑(i=1,k) 2^k = 2^(k+1) - 2 and we need to show that ∑(i=1,k+1) 2^k = 2^(k+2) - 2

∑(i=1,k+1) 2^k = {∑(i=1,k) 2^k} + 2^(k+1) by definition, which, by our hypothosis is (2^(k+1) - 2) + 2^(k+1)

To make this next part a little clearer, let 2^(k+1) be u

So u - 2 + u = 2u - 2 replacing back in gives 2 * 2^(k+1) - 2 which we can write as 2^1 * 2^(k+1) - 2 and properties of exponents tells us that this is the same as 2^(k+1+1)-2 or 2^(k+2) -2.

As for the problem, we still have those initial 4 lines, but it's easy to see that 4 + 2^(n+1) - 2 = 2^(n+1) + 2. Also, for n = 0, 2^(0+1) + 2 gives us 4 as expected, though we didn't cover that in our proof.

The only other issue is efficiently calculating the power. We know that (a*b)%m = (a%m * b%m)%m, and as numbers get extremely large, this greatly reduces the computational power necessary to multiply.

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge