All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Number formation
Tag(s):

Algorithms, Dynamic Programming, Easy, Two dimensional

Problem
Editorial
Analytics

You are given an array $$A$$ of $$N$$ integers. Each integer is a single digit number in the range $$[0\; 9]$$. You are also given a number $$K$$. Now, you need to count how many subsequences of the array $$A$$ exist such that they form a $$K$$ digit valid number.

A subsequence of size $$K$$ is called a valid number if there are no leading zeros in the number formed.

Notes:

  • A subsequence of an array is not necessarily contiguous.
  • Suppose the given array is $$0\;1\;0\;2$$, then if you choose subsequence to be $$002$$, then it is not a valid $$3$$ digit number. Also, it will not be considered as a single digit number. A valid $$3$$ digit number in the array is $$102$$. Please go through the sample I/O for better understanding.

Input Fomat

The first line contains an integer $$N$$ as input denoting the size of the array.
Next line contains $$N$$ space separated integers that denote elements of the array.
Next line contains an integer $$K$$.

Output Format

In the output, you need to print the count of valid $$K$$ digit numbers modulo $$720720$$.

Constraints

$$1 \le N \le 10^5$$
$$1 \le K \le 30$$
$$0 \le A_i \le 9$$

SAMPLE INPUT
5
1 1 0 1 0
3
SAMPLE OUTPUT
9
Explanation

In the given sample following are the possible subsequences that form a valid $$3$$ digit number.
$$[1 , 2 , 3] = 110$$
$$[1 , 2 , 4] = 111$$
$$[1 , 2 , 5] = 110$$
$$[1 , 3 , 4] = 101$$
$$[1 , 3 , 5] = 100$$
$$[1 , 4 , 5] = 110$$
$$[2 , 3 , 4] = 101$$
$$[2 , 3 , 5] = 100$$
$$[2 , 4 , 5] = 110$$
 

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Cars24.com

Challenge Name

Cars24 Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?