TopCoder problem "FriendlySequences" used in TCCC06 Round 1C (Division I Level One)



Problem Statement

    

We call two numbers friendly if they have the same digits, ignoring order or repetition. For example 122213 and 312 are friendly while 145 and 2544411 are not. A sequence is friendly if it contains at least two numbers, and all possible pairs of numbers within it are friendly. Two contiguous subsequences are different if they have a different start index, end index or both.

If we are given the sequence 112, 12, 21, 354, 534345, 345, 2221 then the friendly contiguous subsequences are: {112, 12}, {112, 12, 21}, {12, 21}, {354, 534345}, {354, 534345, 345} and {534345, 345}. {112, 12, 21, 354} is not a friendly contiguous subsequence because 112 and 354 are not friendly numbers and {112, 12, 21, 2221} is not a friendly contignuous subsequence because the elements of the sequence aren't in consecutive positions in the original sequence.

Given a int[] array, you must return number of different friendly contignuous subsequences of array.

 

Definition

    
Class:FriendlySequences
Method:count
Parameters:int[]
Returns:int
Method signature:int count(int[] array)
(be sure your method is public)
    
 

Constraints

-array will have between 0 and 50 elements, inclusive.
-Each element of array will be between 0 and 2000000000, inclusive.
 

Examples

0)
    
{112, 12, 21, 354, 534345, 345, 2221}
Returns: 6
The example in the problem.
1)
    
{10, 1100, 10101, 111, 1111, 11111, 11, 1, 111}
Returns: 18
2)
    
{0, 0, 0, 0}
Returns: 6
We have a total of 6 possible different pairs of start and end indices for friendly subsequences.
3)
    
{123456890, 213456890, 198654320} 
Returns: 3
4)
    
{9}
Returns: 0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6750

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10104&pm=6750

Writer:

Cosmin.ro

Testers:

PabloGilberto , brett1479 , Olexiy , Andrew_Lazarev

Problem categories:

Brute Force