C++, pasted on Jul 20:
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 ``` ```/** * There is a crazy king. * He has a rule that a shopkeeper must label distinct price to every item in his shop. * i.e. No two items can have the same price. * Moreover, he has certain rules about the maximum price an object may have. * For eg: If maximum price for object is 4, shopkeeper may sell it for 1, 2, 3 or 4. * * You are given an array of size same as number if items in shop. * This array contains the maximum price for each item. * Return the number of possible ways shopkeeper may label the item. * [I guess this problem statement is inspired by: http://topcoder.bgcoder.com/print.php?id=2549] */ // Include header files ============================= #include #include #include #include #include // Namespace ======================================== using namespace std; // Bignumber to handle large data case ============== #define BIGNUM_NAMESPACE_START namespace bignums { #define BIGNUM_NAMESPACE_END } BIGNUM_NAMESPACE_START class bignum_exception: public std::exception { public: bignum_exception() {} }; #define THROW_EXCEPTION(X) throw bignum_exception() class COneDigitOperations { char num, carry; struct OperationMaps { char plusArrayN[256][256], plusArrayC[256][256]; char mulArrayN[256][256], mulArrayC[256][256]; OperationMaps() { static const char numToChar[] = "0123456789"; for(int i = 0, ic = '0'; i < 10; ++i, ++ic) for(int j = 0, jc = '0'; j < 10; ++j, ++jc) { const int s = i + j, m = i * j; plusArrayN[ic][jc] = plusArrayN[i][j] = numToChar[s % 10]; plusArrayC[ic][jc] = plusArrayC[i][j] = numToChar[s / 10]; mulArrayN [ic][jc] = mulArrayN [i][j] = numToChar[m % 10]; mulArrayC [ic][jc] = mulArrayC [i][j] = numToChar[m / 10]; } } }; static OperationMaps m; public: enum EBigOperations { ePlus, eMultiply }; COneDigitOperations(char a_, char b_, EBigOperations op_, char c_ = '0') { int a = a_ - '0'; int b = b_ - '0'; if(a > 9) a -= '0'; if(b > 9) b -= '0'; if(a < 0 || a > 9 || b < 0 || b > 9) { THROW_EXCEPTION("Digit out of range"); } switch (op_) { case ePlus: num = m.plusArrayN[a][b]; carry = m.plusArrayC[a][b]; if(c_ != '0' && num++ == '9') ++carry, num = '0'; break; case eMultiply: num = m.mulArrayN[a][b]; carry = m.mulArrayC[a][b]; { carry = m.plusArrayN[ int(m.plusArrayC[ int(num) ][ int(c_) ]) ][ int(carry) ]; num = m.plusArrayN[ int(num) ][ int(c_) ]; } break; default: THROW_EXCEPTION("Operation not supported"); } } char getNum() const { return num; } char getCarry() const { return carry; } }; COneDigitOperations::OperationMaps COneDigitOperations::m; // static class DecimalUnsignedBigNum { string num; private: DecimalUnsignedBigNum &multiplyWith10() { num = "0" + num; return *this; } void prepend(string &s, string::size_type sz) { s += string(sz, '0'); } void trim(string &s); // Remove all trailing zeroes, if string is empty, set it to "0" public: DecimalUnsignedBigNum() : num("0") {} DecimalUnsignedBigNum(unsigned int i) { stringstream ss; ss << i; ss.str().swap( num ); std::reverse( num.begin(), num.end() ); } // Copy constructor, assignation operator, comparision operators (<,= etc) string toStr() const { string rev(num); // I did not overload << because, reverse( rev.begin(), rev.end() ); // user may expect me to handle return rev; // hex, width, fill etc } // operator +, -, /, *, +=, -= ... for int and DecimalUnsignedBigNum DecimalUnsignedBigNum &operator +=(const DecimalUnsignedBigNum &t) { string that(t.num); if( num.size() > that.size() ) prepend( that, num.size() - that.size() ); else prepend( num, that.size() - num.size() ); char currentCarry = '0'; for(string::iterator it = num.begin(), jt = that.begin(); it != num.end(); ++it, ++jt) { COneDigitOperations d(*it, *jt, COneDigitOperations::ePlus, currentCarry); *it = d.getNum(); currentCarry = d.getCarry(); } if(currentCarry != '0') num += currentCarry; return *this; } DecimalUnsignedBigNum &operator *=(unsigned int t) { DecimalUnsignedBigNum result; while(0 != t) { char currentCarry = '0'; char curNum = "0123456789"[t % 10]; t /= 10; DecimalUnsignedBigNum temp; temp.num.clear(); for(string::iterator it = num.begin(); it != num.end(); ++it) { COneDigitOperations m(*it, curNum, COneDigitOperations::eMultiply, currentCarry); temp.num += m.getNum(); currentCarry = m.getCarry(); } if('0' != currentCarry) temp.num += currentCarry; result += temp; this->multiplyWith10(); } return (*this = result); } }; BIGNUM_NAMESPACE_END // Solution to original problem ===================== template bignums::DecimalUnsignedBigNum calculatePossibilites(int (&arr)[sz]) { // Complexity: O(nlogn) sort( arr, arr + sz ); bignums::DecimalUnsignedBigNum ans = 1; for( size_t i = 0; i < sz; ++i ) ans *= max(0U, arr[i] - i); return ans; } // Test cases ====================================== int arr0[] = {5}; // Expect 5 // Possible combinations are {1}, {2}, {3}, {4}, {5} int arr1[] = {1, 2, 3, 4}; // Expect 1 // The only possible combination is {1, 2, 3, 4, 5} int arr2[] = {4, 4, 4, 4}; // Expect 24 // The possible combinations are {1, 2, 3, 4} and all its permutations (4!) int arr3[] = {4, 4, 4, 4, 4}; // Expect 0 // After labeling first for items, there is no possible distinct value left to label last item int arr4[] = {5, 8}; // Expect 35 int arr5[] = {25, 489, 76, 98, 704, 98, 768, 39, 697, 8, 56, 74, 36, 95, 87, 2, 968, 4, 920, 54, 873, 90}; // Expect: Some very large number // Entry point ===================================== int main() { #define TEST(arr) do { cout << "Input: " << arr << endl; cout << "Answer: " << calculatePossibilites(arr).toStr() << endl << endl; } while(false) TEST(arr0); TEST(arr1); TEST(arr2); TEST(arr3); TEST(arr4); TEST(arr5); return 0; } // End of file ===================================== ```

Output:
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ``` ```Input: [5] Answer: 5 Input: [1, 2, 3, 4] Answer: 1 Input: [4, 4, 4, 4] Answer: 24 Input: [4, 4, 4, 4, 4] Answer: 0 Input: [5, 8] Answer: 35 Input: [25, 489, 76, 98, 704, 98, 768, 39, 697, 8, 56, 74, 36, 95, 87, 2, 968, 4, 920, 54, 873, 90] Answer: 3911092310428208225380367629787824128000000 ```