This problem appeared on the Code Sprint 2 competition by InterviewStreet.com (check out my review here).
There are N cards on the table and each has a number between 0 and N. Let us denote the number on the ith card by ci. You want to pick up all the cards. The ith card can be picked up only if at least ci cards have been picked up before it. (As an example, if a card has a value of 3 on it, you can’t pick that card up unless you’ve already picked up 3 cards previously) In how many ways can all the cards be picked up?
Input:
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by integers ci,…,cN on the second line.
Output:
Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007.
Sample Input:
3
3
0 0 0
3
0 0 1
3
0 3 3
Sample Output:
6
4
0
Solution: A simple algorithm to solve this problem is one that starts at step 0 and goes up to step N-1. At each step it counts the number of cards that can be picked and multiplies the answer by it. If we have zeroes on all cards, therefore, the answer will be N!, as at every step we multiply the answer by the number of cards remaining (e.g., with 4 cards you get 4*3*2*1).
#include <iostream>
int countViableCards(int cards[], int size, int x){
int i;
int count = 0;
for (i=0;i<size;i++)
if (cards[i]<=x)
count++;
return count;
}
int findWays (int cards[], int size){
int i;
int result = 1;
int possibleCards;
for (i=0;i<size;i++){
possibleCards = countViableCards(cards,size,i);
if (possibleCards==0)
return 0;
else
result *= (possibleCards - i);
}
return result;
}
int main(){
int cards[20];
int tests, N;
int i,j;
std::cin >> tests;
for (i=0;i<tests;i++){
std::cin >> N;
for (j=0;j<N;j++)
std::cin >> cards[j];
std::cout << findWays(cards,N) << std::endl;
}
return 0;
}
And here’s the solution from one of the top competitors:
#include<iostream>
#include<set>
#include<map>
#include<string>
#include<stdio.h>
#include<sstream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<string.h>
using namespace std ;
#define INF (int)1e9
#define MAXN 50002
#define MOD 1000000007
int n,a[MAXN] ;
int brute()
{
int p[20],ret = 0 ;
for(int i = 0;i < n;i++) p[i] = i ;
do
{
bool valid = true ;
for(int i = 0;i < n;i++) if(a[p[i]] > i) valid = false ;
if(valid) ret++ ;
}
while(next_permutation(p,p + n)) ;
return ret ;
}
int dp[MAXN] ;
int solve()
{
sort(a,a + n) ;
dp[n] = 1 ;
for(int i = n - 1;i >= 0;i--)
{
int low = -1,high = n ;
while(low + 1 < high)
{
int mid = low + (high - low) / 2 ;
if(a[mid] <= i) low = mid ;
else high = mid ;
}
int ct = low + 1 ;
if(ct <= i) dp[i] = 0 ;
else dp[i] = 1LL * (ct - i) * dp[i + 1] % MOD ;
}
return dp[0] ;
}
void gen(int N = 0)
{
if(N == 0) n = rand() % 10 + 1 ;
else n = N ;
for(int i = 0;i < n;i++) a[i] = rand() % min(n,i + 3) ;
}
void test()
{
for(int t = 1;t <= 100;t++)
{
gen() ;
int ret1 = brute() ;
int ret2 = solve() ;
cout << ret1 << " " << ret2 << endl ;
if(ret1 != ret2)
{
cout << "failed on: " << t << endl ;
cout << n << endl ;
for(int i = 0;i < n;i++) cout << a[i] << " " ; cout << endl ;
while(1) ;
}
}
}
void generate()
{
char in[] = "in .txt" ;
for(int test = 0;test < 10;test++)
{
in[2] = test + '0' ;
FILE * fout = fopen(in,"w") ;
int runs = test < 2 ? 5 : 10 ;
fprintf(fout,"%dn",runs) ;
for(int t = 0;t < runs;t++)
{
if(test == 0 || test == 1) n = 20 - rand() % 5 ;
else n = 50000 - rand() % 1000 ;
gen(n) ;
int ret = solve() ;
if(ret == 0) {t-- ; continue ; }
for(int i = 0;i < n;i++) swap(a[i],a[i + rand() % (n - i)]) ;
fprintf(fout,"%dn",n) ;
for(int i = 0;i < n;i++)
{
if(i) fprintf(fout," ") ;
fprintf(fout,"%d",a[i]) ;
}
fprintf(fout,"n") ;
}
}
}
int main()
{
// generate() ; return 0 ;
// test() ; return 0 ;
int runs ;
scanf("%d",&runs) ;
while(runs--)
{
scanf("%d",&n) ;
for(int i = 0;i < n;i++) scanf("%d",&a[i]) ;
for(int i = 0;i < n;i++) if(a[i] < 0 || a[i] > n) while(1) ;
int ret = solve() ;
printf("%dn",ret) ;
}
return 0 ;
}
You can actually run the calculation with a tighter loop:
ulong count = 1UL;
Array.Sort(Cards);
int upToCard = -1;
for (int i = 0; i < Cards.Length && count != 0; i++)
{
// For each position, count the number of possible options and accumulate.
// Update the index of the card up to which we can take.
while (upToCard < Cards.Length – 1 && Cards[upToCard + 1] <= i)
{
++upToCard;
}
// Accumulate the options that we have for i.
int optionCount = upToCard < i ? 0 : upToCard – i + 1;
count = (count * (ulong)optionCount) % MODULE;
}
return count;
The end performance is roughly the same anyway, as sorting the array is the most costly. Still, I would say it's easier to understand than running a binary search on each iteration 🙂
You don’t need to search the index of the card we would like to take, just use i + 1 – cards[i] to calculate the possible ways in current step
static int FindWays( int[] cards )
{
Array.Sort( cards );
int iWays = 1;
for ( int i = cards.Length-1; i>-1; –i )
{
// calculate the possible ways in current step
int k = i + 1 – cards[i];
if ( k<=0 )
{
iWays = 0;
break;
}
iWays *= k;
}
Console.WriteLine( iWays );
return iWays;
}
I don’t understand your solution, where do you ensure that the sum is less than the value of the card.
I have posted the below complete solution to the question at interviewStreet.com
Well, to just find the number of picks only (excluding the complexity of Sorting the sequence) code by “Daniel Scocco” runs in O(N^2) times where as the code submitted by “Top competitor” runs in O(NLogN) time.
I have figured out an algo which runs in O(N) time. If I include the sorting time then my code’s complexity increases to O(NlogN) time. But if I just speak of finding the total number of Picks for a given sequence, it runs in O(N) time.
I am pasting just the code to find the number of picks given the sorted array: seq[] of size len. Sorting is done by me through Quick-Sort algo, code of which is trivial.
And here goes my code:
#define MOD 1000000007
unsigned long NumberOfPics(int *seq, int len)
{
unsigned long pics = 1;
int i = 1;
if(seq == NULL)
return 0;
for(i=1; i=i)
{
pics = 0;
break;
}
pics *= (i – seq[i]);
pics = pics%MOD;
}
return pics%MOD;
}
Explanation:
My convention:
while storing the values in seq[], I have placed length of the input sequence in seq[0].
Therefore my sequence lies in array seq[] from position seq[1] to seq[len].
Logic:
If seq[i] is smaller than i, then value seq[i] at position i can be placed at positions seq[i] to i
(that is number of positions seq[i] can be placed are (i-seq[i]))
Therefore # of pickings are : (i-seq[i])*NumberOfPics(seq, len-1)
Hence, for a given sequence, total number of pics is the product of pics from 1 to len
Note that if at any position i the value of seq[i] is more than or equal to i (i.e. seq[i] >= i) then number of pics is ZERO
some lines in above code by me got altered…heres the correct code:
#define MOD 1000000007
unsigned long NumberOfPics(int *seq, int len)
{
unsigned long pics = 1;
int i = 1;
if(seq == NULL)
return 0;
for(i=1; i=i)
{
pics = 0;
break;
}
pics *= (i – seq[i]);
pics = pics%MOD;
}
return pics%MOD;
}
altered again….this time giving just the corrected lines…
take for loop as:
for ( i=1 ; i = i )
{
pics = 0;
break;
}
I wrote the following code for this problem, I got the first three test cases passed, but faced time limit exceeded error for big cases. Can somebody tell me which part is time consuming and help me to edit it.
def cards(n,array):
total=1;
count=[0 for i in range(n+1)] # initial array to take a count of various numbers
for i in range(n):
count[array[i]]=count[array[i]]+1 # updates the count of numbers of array[i] element obtained O(n) time
totalsum=count[0]; # number of zeroes
for i in range(n):
if i!=0:
totalsum=totalsum+count[i]
total=(totalsum-i)*total # possible choices to pick up cards
else:
total=count[0]*total # initially only )-marked cards can be picked
return total
n=int(input())
output=[0 for i in range(n)]
for i in range(n):
x = int(input())
s = input()
mynums = [int(i) for i in s.split()]
output[i]=cards(x,mynums)
for i in range(n):
print(output[i]/1000000007)