TilingsCount coding task - Learn to Code

Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

UPCOMING CHALLENGES:

CURRENT CHALLENGES:

Bug Wars: The Last Hope

PAST CHALLENGES

The Fellowship of the Code

May the 4th

The Great Code Off 2021

The Doge 2021

The Matrix 2021

The OLX Group challenge

TilingsCount

START

Count tilings of a narrow but long rectangle with tiles of size 1x1 or 2x2.

Programming language:

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

only tiles of size 1x1 and/or 2x2 are used;

each tile of size 1x1 covers exactly one whole square;

each tile of size 2x2 covers exactly four whole squares;

each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

class Solution { public int solution(int N, int M); }

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..1,000,000];

M is an integer within the range [1..7].

TilingsCount

Developer Training

Sign up for our newsletter:

Social: