```
import itertools
def solution(N):
s = list(str(N))
solution = set([ s for s in itertools.permutations(s)])
if len(solution) == 1:
print("1")
return
final_solution = [ s for s in solution if s[0] !='0' ]
print(len(final_solution))
```

```
from operator import mul
def prod(l):
return reduce(mul, l, 1)
def fact(n):
return prod(range(1, n+1))
def num_similar(n):
n = list(str(n))
digits = dict((x, n.count(x)) for x in set(n))
return fact(len(n))/prod(fact(x) for x in digits.values())
```

Multinomial Theorem. @saeidw explained it well!

`Multinomial @@ Last /@ Tally[IntegerDigits[1213]]`

I wish all languages implemented Multinomial, it would have been easier :)

]]>`Multinomial @@ Last /@ Tally[IntegerDigits[1213]]`

i will try to do it when i have time.]]>

An n-digit number has n! permutations. Some values will not be unique. Consider the number 112. It has 3 digits, so 6 permutations. Due to the repetition of the digit 1, we get the same numbers twice:

```
112
112
121
121
211
211
```

In fact, there are three unique numbers in this permutation: 112, 121, and 211. We need to divide the total number of permutations by the number of possible permutations of the repeated digits.

`similarities(n) = length(n)! / sum [ x! | x ∈ repeatedDigits(n) ]`

Of course if there are no repeated digits, the number of similar numbers will always be equal to the number of possible permutations of n.

In Haskell-talk (because I live beyond the rules!):

```
similarities :: Int -> Int
similarities n = (factorial $ length ds) `div` sumOr1 duplicateFactorials
where ds = digits n
repeated (_, y) = y > 1
duplicates = map snd $ filter repeated $ frequencies $ ds
duplicateFactorials = map factorial duplicates
sumOr1 xs = case sum xs of
0 -> 1
s -> s
```

In order to compute *ds* we use the *digits* function which turns the number into a list of digits by first converting it into a string and then reading each digit back individually. It's a dirty trick:

```
digits :: Int -> [Int]
digits x = map (read . (: [])) $ show x
```

In order to detect repeated digits we find the frequencies of occurence of each digit in *ds* by building up an association list (I'm too lazy to use a map). For **1213**, the list looks something like **[(2, 1), (1, 2), (3, 1)]**. We compute this with the *frequencies* function:

```
frequencies :: Eq a => [a] -> [(a, Int)]
frequencies = foldr frequency []
where frequency x zs =
case lookup x zs of
Just n -> update x (n + 1) zs
Nothing -> (x, 1) : zs
```

*frequencies* scans a list of numbers and tries to lookup each number in an association list, if it can't find the number it adds it to the list with a frequency of 1, otherwise it tries to update the association list by incrementing the frequency for that number. The *lookup* function is built-in, the *update* function is pretty simple, can you think of an implementation?

Once we have the list of frequencies of digits in the number, we filter the list to only keep the frequencies of the digits that have been repeated, and we extract those into a new list called *duplicates*. We compute their factorials by mapping the *factorial* function over them. I used a lame recursive factorial, but you can use a faster implementation.

Finally we *sum* the factorials of the duplicate numbers. If there are no duplicates, this sum will be 0, and since we don't like to divide by 0, we'll just replace it with 1 so that the result of the division is just equal to the number of possible permutations.

```
import java.util.Scanner;
public class similarInt {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int N = input.nextInt();
System.out.println(solution(N));
}
public static int solution(int N){
String num = Integer.toString(N);
int length = num.length();
int tots = factorial(length);
int[] a = new int[10];
for(int x=0;x<num.length();x++){
a[Integer.valueOf(String.valueOf(num.charAt(x)))]++;
}
for(int x=0;x<a.length;x++){
tots=tots/factorial(a[x]);
}
return tots;
}
public static int factorial(int n){
int a=1;
for(int i=n;i>=1;i--){
a=a*i;
}
return a;
}
}
```

```
#include <iostream>
#include <vector>
using namespace std;
vector<int> cached(10);
int factoriaFN(int number)
{
if(number <= 1) return 1;
if(cached[number] != -1) return cached[number];
return cached[number] = number * factoriaFN(number -1);
}
int SimilarIntegers(int N)
{
// find how many digits, find how many digits are the same
int numberofdigits = 0;
int digits[10] = {0};
int K = N, M;
while (K != 0) {
M = K;
K /= 10;
digits[M - K * 10]++;
numberofdigits++;
}
// find the factorial of the number of digits
int factorial = factoriaFN(numberofdigits);
for (int i = 0; i < 10; ++i) {
if (digits[i] > 1) { // find its factorial and divide the original factorial by this one
factorial /= factoriaFN(digits[i]);
}
}
return factorial;
}
int main()
{
for(int i=0; i< 10; ++i){
cached[i] = -1;
factoriaFN(i);
}
cout<<SimilarIntegers(1213)<<endl;
return 0;
}
```

```
dp=[];
for(var i=0;i<100;i++){
dp.push([]);
for(var j=0;j<100;j++){
dp[i].push(-1)
}
}
function C(n,k){
if(dp[n][k]!=-1)return dp[n][k];
if(n==k)return 1;
if(k==0)return 1;
return dp[n][k]=C(n-1,k-1)+C(n-1,k);
}
function solutions(N){
N=(N+'');
var ans=1;
var nums=N.length;
for(var i=0;i<10;i++){
var digit=i+'';
var digitCount=0;
for(var j=0;j<N.length;j++){
if(digit==N[j])digitCount++;
}
ans=ans*C(nums,digitCount);
nums-=digitCount;
}
return ans;
}
```

1123 => 12

123 => 6

5511 => 6

55551 => 5

5551 => 4

112 => 3

14 => 2

11 => 1

6 => 1

Accepted languages: C++, C#, Java, Objective-C.

*<admin edit: had to remove this image because of a DMCA takedown notice from codility />*