Counting total number of paper pieces

user_11313748 0
Viewed 159

The below is an interview question which I was unable to solve and needs some help.

Question:

A Person is playing with paper and during his game he folds the paper vertically in one turn and then horizontally in another turn and repeats the process n number of times. After he's done he cuts the paper vertically and horizontally. The task at hand is to take a number "N" as input and find the count of paper pieces that will be there after cutting the paper vertically and horizontally after folding it n times following the pattern as mentioned above.

Constraints:

1< N <10^5

N : Total number of turns
As the answer can be very large output the result mod 10^9+7

Test Cases

Input: 0
Output: 4

Input: 1
Output: 6

Input: 2
Output: 9

Input: 3
Output: 15

I tried to find some number pattern but couldn't find any also this question doesn't seem related to any algorithm and thus I was unable to find any proper approach. Please help suggesting some approach.

number-theory adhoc data-structures algorithm
1 Answers

As the comments mentions, you should look for a pattern in the sections (4 corners) and not in the total parts. We will enumerate the corners as a vector like this:

(a (top left),b (top Right) ,c (bottom left) ,d (bottom Right))

Also for sake of consistency and understanding we always fold from right to left in the vertical fold (right half on top of the left half) and from bottom to top in the horizontal fold (bottom half on top of the top half) and we start with horizontal as the first fold we will preform.

first we start with 1 in each corner so when we divide we get the sum of all corners like this:

(1,1,1,1) = 1 + 1 + 1 + 1 = 4 (n = 0)

lets see what will happen in each corner after few runs:

(2,1,2,1) = 2 + 1 + 2 + 1 = 6 (n = 1)

(4,2,2,1) = 4 + 2 + 2 + 1 = 9 (n = 2)

(6,3,4,2) = 6 + 3 + 4 + 2 = 15 (n = 3)

(9,6,6,4) = 9 + 6 + 6 + 4 = 25 (n = 4)

maybe at first its hard to see the relation between but actually the pattern is pretty simple:

(a,b,c,d) -> (a+b,a,c+d,c) when you fold vertically (from right to left)

and

(a,b,c,d) -> (a+c,b+d,a,b) when you fold horizontally (from bottom to top)

so you can get the recursive relationship and here some simple code in C for this:

int func(int a, int b, int c, int d, int n) {
 if (n == 0) return (a + b + c + d);
 if (n % 2 == 0) return func(a + b, a, c + d, c, n - 1);
 else return func(a + c, b + d, a, b, n - 1);
}

from here you can get a better computational results but this is a start

user_153252950
Related