Hi,
I recently came across this problem in an online hiring test.
Given an integer d, find the number of **pure-number** sequences of length d.
a pure-number sequence is a sequence of digits where any digit (0 - 9) can come at any index i iff -
1. n is 0
2. any divisor of n (except 1) has been placed at an index j ( j < i).
First number can be anything from 1 to 9.
eg - 246 is a pure number
201 is not a pure number, there is no divisor of 1 behind it.
Return the total number of sequences modulo 1e9 + 7
constraints : 1 <= d <= 1000
And here’s what I did
int dp[1001][1025];
int solve1(int i, int& d, int bitmask) {
if(i == d) return 1;
if(dp[i][bitmask] != -1) return dp[i][bitmask];
int ans = 0;
// place the current digit
for(int cur = 0; cur <= 9; cur += 1) {
// check if any of it's divisors have already been placed
for(int j = 0; j <= 11; j += 1) {
if( j == 1 && cur != 1) continue;
if(bitmask & (1<<j)) {
if(j == 0 || cur % j == 0) ans = (ans + solve1(i+1, d, bitmask | (1<<cur))) % MOD;
}
}
}
return dp[i][bitmask] = ans % MOD;
}
void solve(int cs)
{
memset(dp, -1, sizeof(dp));
int n;
cin>>n;
int ans = 0;
int bitmask = 0;
for(int i = 1; i <= 9; i += 1) {
ans += solve1(1, n, bitmask | (1<<i));
ans %= MOD;
}
cout<<ans<<"\n";
}
I am quite sure I have the idea correct, but I couldn’t pass most of the testcases. Any help would be appreciated.
1 Like
Updated:
@codespeed Your solution fails for n = 3 as it gives 164 while the correct answer is 71 according to the problem.
@codespeed Do tag me if you find any counter example for my solution.
Update: I have changed few things. Like adding vis to f function and changing lookup[1].
My Solution:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int mxn = (1 << 9) + 1;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<vector<int>> lookup(10);
lookup[1] = {};
lookup[2] = {2, 4, 6, 8};
lookup[3] = {3, 6, 9};
lookup[4] = {4, 8};
lookup[5] = {5};
lookup[6] = {6};
lookup[7] = {7};
lookup[8] = {8};
lookup[9] = {9};
int n; cin >> n;
int dp[n + 1][mxn];
memset(dp, -1, sizeof dp);
function<int(int, int)> f = [&](int i, int bm) -> int {
if(i == n) return 1;
if(dp[i][bm] != -1) return dp[i][bm];
int ans = 0;
if(i == 0) {
for(int j = 1; j <= 9; j++) {
ans = (ans + f(i + 1, bm | (1 << j))) % mod;
}
} else {
ans = (ans + f(i + 1, bm | (1 << 0))) % mod;
int vis = 0;
for(int j = 1; j <= 9; j++) {
if((1 << j) & bm) {
for(int k: lookup[j]) {
if((vis & (1 << k)) == 0) {
ans = (ans + f(i + 1, bm | (1 << k))) % mod;
vis |= (1 << k);
}
}
}
}
}
return dp[i][bm] = (ans % mod);
};
cout << f(0, 0) << '\n';
return 0;
}
1 Like
@whymihere thanks for your response. But the numbers 10, 11, 12, 13, 14… are invalid. Problem statement says any divisor except 1.
Answer for n = 2 is 23 only.
Could you list all the possible combination for n = 2? @codespeed
only 10 in top row I suppose, rest you mentioned are fine @whymihere
Changing
lookup[1] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
to
lookup[1] = {}; // means once we start with 1 only 0's appear after it eg 10, 100, 1000, ...
Should work I guess? @codespeed
Yeah sorry for the late reply, needed to understand your solution. Yup what you proposed should solve the problem. Could you also tell me the reason for adding this line
ans = (ans + f(i + 1, bm | (1 << 0))) % mod;
in the else block.
I know I am asking too much, but how would you go around writing a brute force solution for this? Writing a test generator is fairly easy for this, but I need to know the solution is absolutely fine.
@codespeed as 0 can appear after anything right. Similar to 10, 20 is also valid so is 30 and so on.
Some things I changed in my solution.
- Added vis so that same function in not called multiple time as one digit can have multiple divisor before it.
- As you pointed out by you only 0 can appear after 1.
I will drop the brute force solution here:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int mxn = (1 << 9) + 1;
int brute(int n) {
int ans = 0;
function<void(vector<int>)> f = [&](vector<int> v) -> void {
if((int)v.size() == n) {
// To print all the valid number commnet the section below
// for(auto& e: v) cout << e; cout << '\n';
ans++;
return;
}
if(v.size() == 0) {
for(int i = 1; i <= 9; i++) {
v.push_back(i);
f(v);
v.pop_back();
}
} else {
v.push_back(0);
f(v);
v.pop_back();
set<int> seen;
for(int i = 1; i <= 9; i++) {
for(auto& e: v) {
if((e != 1 and e != 0) and i % e == 0 and seen.find(i) == seen.end()) {
v.push_back(i);
f(v);
v.pop_back();
seen.insert(i);
}
}
}
}
};
f({});
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<vector<int>> lookup(10);
lookup[1] = {};
lookup[2] = {2, 4, 6, 8};
lookup[3] = {3, 6, 9};
lookup[4] = {4, 8};
lookup[5] = {5};
lookup[6] = {6};
lookup[7] = {7};
lookup[8] = {8};
lookup[9] = {9};
int n; cin >> n;
int dp[n + 1][mxn];
memset(dp, -1, sizeof dp);
function<int(int, int)> f = [&](int i, int bm) -> int {
if(i == n) return 1;
if(dp[i][bm] != -1) return dp[i][bm];
int ans = 0;
if(i == 0) {
for(int j = 1; j <= 9; j++) {
ans = (ans + f(i + 1, bm | (1 << j))) % mod;
}
} else {
ans = (ans + f(i + 1, bm | (1 << 0))) % mod;
int vis = 0;
for(int j = 1; j <= 9; j++) {
if((1 << j) & bm) {
for(int k: lookup[j]) {
if((vis & (1 << k)) == 0) {
ans = (ans + f(i + 1, bm | (1 << k))) % mod;
vis |= (1 << k);
}
}
}
}
}
return dp[i][bm] = (ans % mod);
};
cout << "brute = " << brute(n) << '\n';
cout << "ans = " << f(0, 0) << '\n';
return 0;
}
1 Like
Thanks for the really neat solutions. I picked up some pretty good techniques from you. Thanks a bunch! @whymihere
1 Like