A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

Pages: **1**

**jsaade****Member**

I am not sure if this was posted before, it is from codility, but it is a bit fun to solve.

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

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

**rolf****Member**

It's mind boggling. I did some test calculations (see below). I'm sure there is a pattern/equation, but I can't quite get my head around it.

1123 => 12

123 => 6

5511 => 6

55551 => 5

5551 => 4

112 => 3

14 => 2

11 => 1

6 => 1

*Last edited by rolf (September 22 2014)*

**Ra8****Member**

My code works as the expected complexity. I just didn't account for leading zeros. I also wrote it in JS it really easy to translate it to C++ or any other language..

```
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;
}
```

*Last edited by Ra8 (September 22 2014)*

**jsaade****Member**

c++

```
#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;
}
```

*Last edited by jsaade (September 23 2014)*

**m.sabra****Member**

Java

```
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;
}
}
```

**saeidw****Member**

This was a fun exercise. Once I understood the relationship between similar numbers and the permutations of a number with respect to the repeated digits it contains, the whole thing started making sense.

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.

**NuclearVision****Member**

i think there is a similar exercice on project euler.

i will try to do it when i have time.

**geek****Member**

Multinomial Theorem. @saeidw explained it well!

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

**jsaade****Member**

geek wrote:

Multinomial Theorem. @saeidw explained it well!

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

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

**raja****Member**

Haven't been here in a while, but felt like visiting, obligatory python 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())
```

**varbha****Member**

Condensed Python solution

```
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))
```

Pages: **1**