count-good-numbers

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (<code>2</code>, <code>3</code>, <code>5</code>, or <code>7</code>).

<ul>
	<li>For example, <code>&quot;2582&quot;</code> is good because the digits (<code>2</code> and <code>8</code>) at even positions are even and the digits (<code>5</code> and <code>2</code>) at odd positions are prime. However, <code>&quot;3245&quot;</code> is not good because <code>3</code> is at an even index but is not even.</li>
</ul>

Given an integer <code>n</code>, return the total number of good digit strings of length <code>n</code>. Since the answer may be large, return it modulo <code>109 + 7</code>.

A digit string is a string consisting of digits <code>0</code> through <code>9</code> that may contain leading zeros.

&nbsp;
Example 1:

<pre>
Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are &quot;0&quot;, &quot;2&quot;, &quot;4&quot;, &quot;6&quot;, &quot;8&quot;.
</pre>

Example 2:

<pre>
Input: n = 4
Output: 400
</pre>

Example 3:

<pre>
Input: n = 50
Output: 564908303
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 1015</code></li>
</ul>

countGoodNumbers

Count Good Numbers

Count the Number of Arrays with K Matching Adjacent Elements

count-the-number-of-arrays-with-k-matching-adjacent-elements

统计恰好有 K 个相等相邻元素的数组数目

Recursion

Math

我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （<code>2</code>，<code>3</code>，<code>5</code> 或 <code>7</code>）。

<ul>
	<li>比方说，<code>"2582"</code> 是好数字，因为偶数下标处的数字（<code>2</code> 和 <code>8</code>）是偶数且奇数下标处的数字（<code>5</code> 和 <code>2</code>）为质数。但 <code>"3245"</code> 不是 好数字，因为 <code>3</code> 在偶数下标处但不是偶数。</li>
</ul>

给你一个整数 <code>n</code> ，请你返回长度为 <code>n</code> 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 <code>109 + 7</code> 取余后返回 。

一个 数字字符串 是每一位都由 <code>0</code> 到 <code>9</code> 组成的字符串，且可能包含前导 0 。

 

示例 1：

<pre>
输入：n = 1
输出：5
解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。
</pre>

示例 2：

<pre>
输入：n = 4
输出：400
</pre>

示例 3：

<pre>
输入：n = 50
输出：564908303
</pre>

 

提示：

<ul>
	<li><code>1 <= n <= 1015</code></li>
</ul>