Statement

Suppose there is a game where a player can score either 11, 22, or 44 points in each turn. Given a total score, nn, find all the possible ways in which you can score these nn points.

Note: You may assume that you can use a specific score as many times as you want. Additionally, the order in which we select scores from the list is significant.

Let's say the total points to be earned are 33. A player can score this total in the following three ways:

  • 1,11, 1and 11, in three turns: 1+1+1=31+1+1 = 3.

  • 11 and then a 22, in two turns: 1+2=31 + 2 = 3.

  • 22 and then a 11, in two turns: 2+1=32 + 1 = 3.

Constraints:

  • 00 <= nn <= 900900

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.