This was asked in online round of google singapore for internship.
Given an array S of N element. We need to find count of distinct arrays A of N elements exists such that :
-
A[i] < A[i+1] for all 1<= i<N
-
Sum of digit of A[i] is equal to S[i] for all 1<=i<=N
-
1<=A[i]<=1000
An array A is said to be different from array B if there exist an index i such that A[i] != B[i].
Since the count can be very large, print answer modulo 109 + 7.
Consider one based indexing
Input format
• First line contains an integer T, denoting number of test cases. For each test case
• First line contains an integer N.
. Second line contains N space separated integers, denoting array S
Output format
For each test case on the required anwer in a new line.
Constraints:
1<=T<=5
1<=N<=100
1<=S[i]<=30
Input:
T=1
N=2
S=[2,1]
Input: T=1,N=2, S= [2,1]
Output: 10
My solution: not able to solve during contest but tried later and came up with this, Can anyone comment down correct solution or point out my mistake
#include<bits/stdc++.h>
using namespace std;
int func(int i){
int c = 0;
while(i!=0){
c += i % 10;
i /= 10;
}
return c;
}
int main()
{
int n;
cin>>n;
vectorv;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
v.push_back(x);
}
vector<vector<int>>dp(n+1,vector<int>(1001,0));
for(int i=n-1;i>=0;i--)
{
if(i==n-1)
{
int val=func(v[i]);
int prev=-1;
for(int j=1000;j>0;j--)
{
int curr=func(j);
if(curr==val)
{
dp[i][j]++;
if(prev==-1)
{
prev=j;
}
else
{
for(int k=j;k<prev;k++)
{
dp[i][k]+=dp[i][prev];
}
prev=j;
}
}
}
}
else
{
int val=func(v[i]);
int prev=-1;
for(int j=1000;j>0;j--)
{
int curr=func(j);
if(curr==val)
{
if(prev==-1)
{
prev=j;
}
else
{
for(int k=j+1;k<prev;k++)
{
dp[i][k]+=dp[i][prev];
}
prev=j;
}
dp[i][j]=dp[i+1][j+1]+ dp[i][j+1];
}
}
}
}
int ans;
for(int i=0;i<=1000;i++)
{
if(dp[0][i]!=0)
{
ans=dp[0][i];
break;
}
}
cout<<ans;
}