Posted on | In , |
Words count in article: 171 | Reading time ≈ 1

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:

Input:
11110
11010
11000
00000

Output: 1
Example 2:

Input:
11000
11000
00100
00011

Output: 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   void DFS(vector<vector<char>>& grid, int i, int j){
    if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()) return;
    if('0' == grid[i][j]) return;
    grid[i][j] = '0';
    DFS(grid, i-1, j);
    DFS(grid, i+1, j);
    DFS(grid, i, j - 1);
    DFS(grid, i, j + 1);
}
int numIslands(vector<vector<char>>& grid) {
	int counter = 0;
	for (int i = 0; i < grid.size(); ++i)
		for (int j = 0; j < grid[i].size(); ++j)
			if ('1' == grid[i][j])
			{
				++counter;
				DFS(grid, i, j);
			}
	return counter;
}

Posted on | In , |
Words count in article: 94 | Reading time ≈ 1

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

1
2
3
Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

1
2
3
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

1
2
3
4
5
6
7
8
9
10
int numSquares(int n) {
    static vector<int> dp {0};
    while (dp.size() <= n) {
        int m = dp.size(), squares = INT_MAX;
        for (int i=1; i*i<=m; ++i)
            squares = min(squares, dp[m-i*i] + 1);
        dp.push_back(squares);
    }
    return dp[n];
}

Posted on | In , |
Words count in article: 188 | Reading time ≈ 1

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

1
2
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?
1
2
3
4
5
6
7
8
9
10
11
void sortColors(vector<int>& nums) {
    int zero =0, l = 0, r = nums.size()-1;
    while (l <= r) {
        if (nums[l] == 0) 
            swap(nums[l++], nums[zero++]);
        else if (nums[l] == 2) 
            swap(nums[l], nums[r--]);
        else
            l++;
    }
}

Posted on | In , |
Words count in article: 158 | Reading time ≈ 1

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    1
   / \
  2   5
 / \   \
3   4   6
The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void flatten(TreeNode* root) {
        
        if(root == nullptr) {
            return;
        }
        
        helper(root);
    }
private:
    TreeNode* pre = nullptr;
    void helper(TreeNode* root) {
        
        if(root != nullptr) { 
            helper(root->right);
            helper(root->left);
            root->right = pre;
            root->left = nullptr;
            pre = root;
        }
    }
};
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode pre;
    
    public void flatten(TreeNode root) {
        if(root == null)
            return;
        
        helper(root);
    }
    
    public void helper(TreeNode root){
        if(root != null)
        {
            helper(root.right);
            helper(root.left);
            root.right = pre;
            root.left = null;
            pre = root;
        }
    }
}

Posted on | In , |
Words count in article: 311 | Reading time ≈ 1

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:

1
2
3
4
5
6
7
8
9
10
11
12
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        Helper(root, result, 0);
        return result;
    }
    void Helper(TreeNode* root, vector<vector<int>> &result, int h){
        if (!root) return;

        if (result.size()<h+1){
            vector<int> tmp;
            tmp.push_back(root->val);
            result.push_back(tmp);
        }else{
            result[h].push_back(root->val);
        }
        Helper(root->left, result, h+1);
        Helper(root->right, result, h+1);
    }
};
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
        
        if(root == null) return wrapList;
        
        queue.offer(root);
        while(!queue.isEmpty()){
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<Integer>();
            for(int i=0; i<levelNum; i++) {
                if(queue.peek().left != null) queue.offer(queue.peek().left);
                if(queue.peek().right != null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            wrapList.add(subList);
        }
        return wrapList;
    }
}

Posted on | In , |
Words count in article: 299 | Reading time ≈ 1

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

1
2
3
4
5
6
7
8
9
10
Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int rob(TreeNode* root) 
    {
        std::pair<int, int> m = helper(root);
        return std::max(m.first, m.second);
    }
    
    std::pair<int, int> helper(TreeNode* root)
    {
        if(!root) return {0, 0};
        
        auto leftMoney = helper(root->left);
        auto rightMoney = helper(root->right);
        
        return {root->val + leftMoney.second + rightMoney.second,
                std::max(leftMoney.first, leftMoney.second) 
                + std::max(rightMoney.first, rightMoney.second)};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int[] ret = robHelper(root);
        return Math.max(ret[0], ret[1]);
    }
    
    private int[] robHelper(TreeNode root) {
        int[] ret = new int[2];
        if (root == null) return ret;
        int[] lRet = robHelper(root.left);
        int[] rRet = robHelper(root.right);
        
        ret[0] = Math.max(lRet[0], lRet[1]) + Math.max(rRet[0], rRet[1]);
        ret[1] = lRet[0] + rRet[0] + root.val;
        return ret;
    }
}

Posted on | In , |
Words count in article: 225 | Reading time ≈ 1

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

we set dp[n] is the number of BST that store n consecutive values
we can get dp[n] as follows:

we set 1 as root node, so left subtree has 0 children, right subtree has n - 1 children, the number of bst is dp[0] * dpn - 1;

we set 2 as root node, so left subtree has 1 children, right subtree has n - 2 children, the number of bst is dp[1] * dp[n - 2];

generally, we set k as root noode, so left subtree has k - 1 children, right subtree has n - k children, the number of bst is dp[k - 1] * dp[n - k];

dp[n] = d[0] dp[n - 1] + … + dp[k - 1] dp[n - k] + … + dp[n - 1] * dp[0];

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= i; ++k) {
                dp[i] += dp[k - 1] * dp[i - k];
            }
        }
        return dp[n];
    }
};

Posted on | In , |
Words count in article: 390 | Reading time ≈ 2

Given an array of strings, group anagrams(相同字母异序词) together.

Example:

1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

All inputs will be in lowercase.

The order of your output does not matter.

题解：

C++ unordered_map and counting sort

Use an unordered_map to group the strings by their sorted counterparts. Use the sorted string as the key and all anagram strings as the value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string s : strs) {
            string t = s; 
            sort(t.begin(), t.end());
            mp[t].push_back(s);
        }
        vector<vector<string>> anagrams;
        for (auto p : mp) { 
            anagrams.push_back(p.second);
        }
        return anagrams;
    }
};

Moreover, since the string only contains lower-case alphabets, we can sort them using counting sort to improve the time complexity.

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
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string s : strs) {
            mp[strSort(s)].push_back(s);
        }
        vector<vector<string>> anagrams;
        for (auto p : mp) { 
            anagrams.push_back(p.second);
        }
        return anagrams;
    }
private:
    string strSort(string s) {
        int counter[26] = {0};
        for (char c : s) {
            counter[c - 'a']++;
        }
        string t;
        for (int c = 0; c < 26; c++) {
            t += string(counter[c], c + 'a');
        }
        return t;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String keyStr = String.valueOf(ca);
            if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<String>());
            map.get(keyStr).add(s);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

Posted on | In , |
Words count in article: 1.3k | Reading time ≈ 8 
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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
#include <string>
#include <iostream>
#include <iosfwd>
#include <cmath>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <cstring>
#define MAX_L 2005
using namespace std;

#define max(a,b) a>b ? a:b
#define min(a,b) a<b ? a:b

class bign
{
public:
	int len, s[MAX_L];//数的长度，记录数组
	bool sign; // 符号 1正数 0负数
	bign();
	bign(const char*);
	bign(int);
	string toStr() const; //转化为字符串，主要是便于输出
	friend istream& operator>>(istream &, bign &)
	friend ostream& operator<<(ostream &, bign &);
	//重载=
	bign operator=(const char*)
	bign operator=(int);
	bign operator=(const string);
	//重载比较
	bool operator>(const bign &) const;
	bool operator>=(const bign &) const;
	bool operator<(const bign &) const;
	bool operator<=(const bign &) const;
	bool operator==(const bign &) const;
	bool operator!=(const bign &) const;
	//重载四则运算
	bign operator+(const bign &) const;
	bign operator++();
	bign operator++(int);
	bign operator+=(const bign &);

	bign operator-(const bign &) const;
	bign operator--();
	bign operator--(int);
	bign operator-=(const bign &);

	bign operator*(const bign &) const;
	bign operator*(const int num) const;
	bign operator*=(const bign &);

	bign operator/(const bign &) const;
	bign operator/=(const bign &);
	//四则运算衍生运算
	bign operator%(const bign &) const;
	bign factorial()const;
	bign Sqrt()const;
	bign pow(const bign &)const;

	void clean();
	~bign();
}

bign::bign()
{
	memset(s, 0, sizeof(s));
	len = 1;
	sign = 1;
}

bign::bign(const char *num)
{
	*this = num;
}

bign::bign(int num)
{
	*this = num;
}

stirng bign::toStr()const
{
	string res;
	res = "";
	for(int i=0; i<len; i++)
		res = (char)(s[i]+'0') + res;
	if(res == "")
		res = "0";
	if(!sign && res != "0")
		res = "-" + res;
	return res;
}

istream &operator>>(istream &in, bign &num)
{
	string str;
	in >> str;
	num = str;
	return in;
}

ostream &operator<<(ostream &out, bign &num)
{
    out<<num.toStr();
    return out;
}
 
bign bign::operator=(const char *num)
{
    memset(s, 0, sizeof(s));
    char a[MAX_L] = "";
    if (num[0] != '-')
        strcpy(a, num);
    else
        for (int i = 1; i < strlen(num); i++)
            a[i - 1] = num[i];
    sign = !(num[0] == '-');
    len = strlen(a);
    for (int i = 0; i < strlen(a); i++)
        s[i] = a[len - i - 1] - 48;
    return *this;
}

bign bign::operator=(int num)
{
    if (num < 0)
        sign = 0, num = -num;
    else
        sign = 1;
    char temp[MAX_L];
    sprintf(temp, "%d", num);
    *this = temp;
    return *this;
}
 
bign bign::operator=(const string num)
{
    const char *tmp;
    tmp = num.c_str();
    *this = tmp;
    return *this;
}
 
bool bign::operator<(const bign &num) const
{
    if (sign^num.sign)
        return num.sign;
    if (len != num.len)
        return len < num.len;
    for (int i = len - 1; i >= 0; i--)
        if (s[i] != num.s[i])
            return sign ? (s[i] < num.s[i]) : (!(s[i] < num.s[i]));
    return !sign;
}
 
bool bign::operator>(const bign&num)const
{
    return num < *this;
}
 
bool bign::operator<=(const bign&num)const
{
    return !(*this>num);
}
 
bool bign::operator>=(const bign&num)const
{
    return !(*this<num);
}
 
bool bign::operator!=(const bign&num)const
{
    return *this > num || *this < num;
}
 
bool bign::operator==(const bign&num)const
{
    return !(num != *this);
}

bign bign::operator+(const bign &num)const
{
	if(sign^num.sign)
	{
		bign tmp = sign ? num : *this;
		tmp.sign = 1;
		return sign ? *this-tmp : num-tmp;
	}
	bign result;
	result.len = 0;
	int temp = 0;
	for(int i=0; temp || i < (max(len,num.len)); i++)
	{
		int t = s[i] + num.s[i] + temp;
		result.s[result.len++] = t % 10;
		temp = t / 10;
	}
	result.sign = sign;
	return result;
}


bign bign::operator++()
{
    *this = *this + 1;
    return *this;
}

bign bign::operator++(int)
{
    bign old = *this;
    ++(*this);
    return old;
}

bign bign::operator+=(const bign &num)
{
    *this = *this + num;
    return *this;
}


bign bign::operator-(const bign &num) const
{
	bign b=num, a=*this;
	if(!num.sign && !sign)
	{
		b.sign = 1;
		a.sign = 1;
		return b-a;
	}
	if(!b.sign)
	{
		b.sign = 1;
		return a+b;
	}
	if(!a.sign)
	{
		a.sign = 1;
		b = bign(0) - (a + b);
		return b;
	}
	if(a < b)
	{
		bign c = (b-a);
		c.sign = false;
		return c;
	}
	bign result;
	result.len = 0;
	for(int i=0, g=0; i<a.len; i++)
	{
		int x = a.s[i] - g;
		if(i < b.len) x -= b.s[i];
		if(x >= 0) 
			g = 0;
		else
		{
			g = 1;
			x += 10;
		}
		result.s[result.len++] = x;
	}
	result.clean();
	return result;
}

bign bign::operator * (const bign &num)const
{
    bign result;
    result.len = len + num.len;
 
    for (int i = 0; i < len; i++)
        for (int j = 0; j < num.len; j++)
            result.s[i + j] += s[i] * num.s[j];
 
    for (int i = 0; i < result.len; i++)
    {
        result.s[i + 1] += result.s[i] / 10;
        result.s[i] %= 10;
    }
    result.clean();
    result.sign = !(sign^num.sign);
    return result;
}
 
bign bign::operator*(const int num)const
{
    bign x = num;
    bign z = *this;
    return x*z;
}
bign bign::operator*=(const bign&num)
{
    *this = *this * num;
    return *this;
}

bign bign::operator/(const bign& num)const
{
	bign ans;
	ans.len = len - num.len + 1;
	if(ans.len < 0)
	{
		ans.len = 1;
		return ans;
	}

	bign divisor = *this, divid = num;
	divisor.sign = divid.sign = 1;
	int k = ans.len - 1;
	int j = len - 1;
	while(k >= 0)
	{
		while(divisor.s[j] == 0) j--;
		if(k > j) k = j;
		char z[MAX_L];
		memset(z, 0, sizeof(z));
		for (int i = j; i >= k; i--)
            z[j - i] = divisor.s[i] + '0';
        bign dividend = z;
        if (dividend < divid) { k--; continue; }
        int key = 0;
        while (divid*key <= dividend) key++;
        key--;
        ans.s[k] = key;
        bign temp = divid*key;
        for (int i = 0; i < k; i++)
            temp = temp * 10;
        divisor = divisor - temp;
        k--;
	}
	ans.clean();
    ans.sign = !(sign^num.sign);
    return ans;
}

bign bign::operator/=(const bign&num)
{
    *this = *this / num;
    return *this;
}
 
bign bign::operator%(const bign& num)const
{
    bign a = *this, b = num;
    a.sign = b.sign = 1;
    bign result, temp = a / b*b;
    result = a - temp;
    result.sign = sign;
    return result;
}
 
bign bign::pow(const bign& num)const
{
    bign result = 1;
    for (bign i = 0; i < num; i++)
        result = result*(*this);
    return result;
}
 
bign bign::factorial()const
{
    bign result = 1;
    for (bign i = 1; i <= *this; i++)
        result *= i;
    return result;
}
 
void bign::clean()
{
    if (len == 0) len++;
    while (len > 1 && s[len - 1] == '\0')
        len--;
}
 
bign bign::Sqrt()const
{
    if(*this<0)return -1;
    if(*this<=1)return *this;
    bign l=0,r=*this,mid;
    while(r-l>1)
    {
        mid=(l+r)/2;
        if(mid*mid>*this)
            r=mid;
        else 
            l=mid;
    }
    return l;
}
 
bign::~bign()
{
}

bign num0,num1,res;
 
int main()
{
    cin>>num0>>num1;
    res=num0+num1;
    cout<<res<<endl;
 
    num0=5;
    num1="71";
    res=num0-num1;
    cout<<res<<endl;
 
    res=num0.Sqrt();
    cout<<res<<endl;
 
    res=num0.pow(5);
    cout<<res<<endl;
    return 0;
}

Posted on | In , |
Words count in article: 165 | Reading time ≈ 1

采用数组存储

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
// 1000 的阶乘 2568 位  
#include <stdio.h>  
  
int a[3000];  
  
void show(int k)  
{  
    int i=0;  
    printf("位数 %d 位\n",k);  
    for (i=k-1; i>=0; i--)  
    {  
        printf("%d",a[i]);  
    }  
}  
  
int fanc(int n)  
{  
    int w=0;  
    int i=0, j=0;  
    int t=n;  
    int k=0;    // 表示数据的位数。  
  
    i=0, k=0;  
    while(t)  
    {  
        a[i++] = t%10;  
        t/=10;  
        k++;  
    }  
  
    for (j=n-1; j>1; j--)  
    {  
        w=0;    // 表示进位  
        for (i=0; i<k; i++)  
        {  
            t = a[i]*j+w;  
            a[i] = t%10;  
            w = t/10;  
        }  
  
        while(w)  
        {  
            a[i++] = w%10;  
            w/=10;  
            k++;  
        }  
    }  
    return k;  
}  
  
  
int main()  
{  
    int n;  
    int k=0;  
  
    scanf("%d",&n);  
    k = fanc(n);  
    show(k);  
    printf("\n");  
    return 0;  
}