Birthday Gift: Counting integer Arrays with interesting properties
Your birthday is coming soon and one of your friends, Alex, is thinking about a gift for you. He knows that you really like integer arrays with interesting properties.
He selected two numbers, N and K, and decided to write down on paper all integer arrays of length K (in form a[1], a[2], …, a[K]), where every number a[i] is in range from 1 to N, and, moreover, a[i+1] is divisible by a[i] (where 1 < i <= K), and give you this paper as a birthday present.
Alex is very patient, so he managed to do this. Now you’re wondering, how many different arrays are written down on this paper? Since the answer can be really large, print it modulo 10000.
Example:
Input: N = 3, K = 2
Output: 5
Explanation: All possible arrays are: [1, 1], [1, 2], [1, 3], [2, 2], [3, 3].
Naïve Solution: The basic idea to solve the problem is as follows:
The naïve solution consists of two nested loops that build all possible arrays and then check whether each array meets the stated constraints (1< i = K and a[i+1] is divisible by a[i]). It returns the count of the number of valid arrays.
Time Complexity: O(10k)
Auxiliary Space: O(1)
Efficient approach: We can solve this problem using below algorithm:
- Read the values ‘N’ and ‘K’ from the input.
- Create a helper function called ‘counter’ to count the number of valid arrays of length 2. Set the ‘count’ variable to 0.
- If ‘K’ is 1, return ‘N’ since ‘N’ arrays of length 1 exist between 1 and ‘N’.
- If ‘K’ is 2, use the ‘counter’ function to determine how many valid arrays of length 2 there are.
- If ‘K’ is greater than 2, find ‘mid’ by dividing ‘K’ by 2.
- Run the ‘count’ function iteratively with the arguments ‘N’ and ‘K – mid’ to get the count of arrays containing ‘K – mid’ elements.
- Run the ‘counter’ function recursively with the arguments ‘N’ and ‘mid’ to get the count of arrays containing ‘mid’ elements.
- Add the counts from the two recursive calls and remove 1 to eliminate the overlap when the last element of the first subproblem and the first element of the second subproblem are the same.
- Return the final count modulo 10000 as a response.
Below is the implementation of the above idea:
#include <iostream>
#include <vector>
using namespace std;
// Function to count the number of valid arrays of length
// 'k'
int countValidArrays(int n, int k)
{
// dp[i][j] represents the number of valid arrays of
// length i ending with element j
vector<vector<int> > dp(k + 1, vector<int>(n + 1, 0));
// Base case: There are 'n' arrays of length 1, each
// ending with a different number from 1 to 'n'
for (int j = 1; j <= n; j++) {
dp[1][j] = 1;
}
// Fill the dp array
for (int len = 2; len <= k; len++) {
for (int end = 1; end <= n; end++) {
for (int prev = 1; prev <= n; prev++) {
if (end % prev == 0) {
dp[len][end] += dp[len - 1][prev];
}
}
}
}
// Sum up all valid arrays of length 'k'
int result = 0;
for (int j = 1; j <= n; j++) {
result += dp[k][j];
}
return result;
}
int main()
{
// Input values for 'n' and 'k'
int n = 3;
int k = 2;
// Calculate and print the number of different arrays
cout << countValidArrays(n, k) << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static int countValidArrays(int n, int k) {
int[][] dp = new int[k + 1][n + 1];
for (int j = 1; j <= n; j++) {
dp[1][j] = 1;
}
for (int len = 2; len <= k; len++) {
for (int end = 1; end <= n; end++) {
for (int prev = 1; prev <= n; prev++) {
if (end % prev == 0) {
dp[len][end] += dp[len - 1][prev];
}
}
}
}
int result = 0;
for (int j = 1; j <= n; j++) {
result += dp[k][j];
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = 3;
int k = 2;
System.out.println(countValidArrays(n, k));
}
}
def count_valid_arrays(n, k):
dp = [[0] * (n + 1) for _ in range(k + 1)]
for j in range(1, n + 1):
dp[1][j] = 1
for length in range(2, k + 1):
for end in range(1, n + 1):
for prev in range(1, n + 1):
if end % prev == 0:
dp[length][end] += dp[length - 1][prev]
result = sum(dp[k][j] for j in range(1, n + 1))
return result
n = 3
k = 2
print(count_valid_arrays(n, k))
using System;
class Program {
public static int CountValidArrays(int n, int k)
{
int[, ] dp = new int[k + 1, n + 1];
// Base case: There are 'n' arrays of length 1, each
// ending with a different number from 1 to 'n'
for (int j = 1; j <= n; j++) {
dp[1, j] = 1;
}
// Fill the dp array
for (int len = 2; len <= k; len++) {
for (int end = 1; end <= n; end++) {
for (int prev = 1; prev <= n; prev++) {
if (end % prev == 0) {
dp[len, end] += dp[len - 1, prev];
}
}
}
}
// Sum up all valid arrays of length 'k'
int result = 0;
for (int j = 1; j <= n; j++) {
result += dp[k, j];
}
return result;
}
static void Main(string[] args)
{
// Input values for 'n' and 'k'
int n = 3;
int k = 2;
// Calculate and print the number of different
// arrays
Console.WriteLine(CountValidArrays(n, k));
}
}
function countValidArrays(n, k) {
let dp = Array.from({ length: k + 1 }, () => Array(n + 1).fill(0));
for (let j = 1; j <= n; j++) {
dp[1][j] = 1;
}
for (let len = 2; len <= k; len++) {
for (let end = 1; end <= n; end++) {
for (let prev = 1; prev <= n; prev++) {
if (end % prev === 0) {
dp[len][end] += dp[len - 1][prev];
}
}
}
}
let result = 0;
for (let j = 1; j <= n; j++) {
result += dp[k][j];
}
return result;
}
let n = 3;
let k = 2;
console.log(countValidArrays(n, k));
Output
5
Time Complexity: O(n^2 * log(k))
Auxiliary Space: O(1)