ManyHashes | Topcoder Archive

Problem Statement

Suppose you have a string S of digits, with each digit between 0 and 2 inclusive. We can treat S as a number in ternary (base 3). Ternary is similar to binary, except in ternary the digits represent powers of 3 instead of powers of 2. We compute the hash of S as follows:

	integer hash = 0
	for (integer pos = 0 to LengthOfS-1 inclusive) {
		hash = hash + pos*pos*(value of digit in position pos of S)
        }
	hash = hash + (value of S interpreted as a number in ternary)

The value of the digit 0 is 0, 1 is 1, and 2 is 2. Given an int len, return the sum of the hashes of all strings of length len composed of 0's, 1's, and 2's. Note that these strings may have leading zeros.

Definition

Class:: ManyHashes
Method:: sumHash
Parameters:: int
Returns:: int
Method signature:: int sumHash(int len)
(be sure your method is public)

Constraints

len will be between 1 and 10 inclusive.

Examples

```
1
```
```
Returns: 3
```
The possible strings of length 1 are (quotes for clarity): "0", "1", and "2". Their hashes are 0, 1, and 2 respectively. The sum gives 3.
```
2
```
```
Returns: 45
```
The possible strings are (quotes for clarity): "00", "01", "02", "10", "11", "12", "20", "21", "22". The hash values are stated below: String - Hash | String - Hash 00 0 | 12 - 7 01 2 | 20 - 6 02 4 | 21 - 8 10 3 | 22 - 10 11 5 |
```
5
```
```
Returns: 36693
```
As an example, the hash of 11022 is example below: a) First we account for the digit values: Digit - Position - Total Value 1 0 0 1 1 1 0 2 0 2 3 18 2 4 32 -------------------------------------------- Total 51 b) Interpreting 11022 as a ternary (base 3) number, we compute its decimal value: 1*81 + 1*27 + 0*9 + 2*3 + 2*1 = 116 Thus the hash of 11022 is 167. As another example, the hash of 02122 is 127.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.