LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 September 22 2014

jsaade
Member

[Exercise] Similar Integers

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 />

Offline

#2 September 22 2014

rolf
Member

Re: [Exercise] Similar Integers

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)

Offline

#3 September 22 2014

Ra8
Member

Re: [Exercise] Similar Integers

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)

Offline

#4 September 23 2014

jsaade
Member

Re: [Exercise] Similar Integers

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)

Offline

#5 September 23 2014

m.sabra
Member

Re: [Exercise] Similar Integers

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

Offline

#6 September 23 2014

saeidw
Member

Re: [Exercise] Similar Integers

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.

Offline

#7 September 24 2014

NuclearVision
Member

Re: [Exercise] Similar Integers

i think there is a similar exercice on project euler.
i will try to do it when i have time.

Offline

#8 September 25 2014

geek
Member

Re: [Exercise] Similar Integers

Multinomial Theorem. @saeidw explained it well!

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

Offline

#9 September 25 2014

jsaade
Member

Re: [Exercise] Similar Integers

geek wrote:

Multinomial Theorem. @saeidw explained it well!

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

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

Offline

#10 September 26 2014

raja
Member

Re: [Exercise] Similar Integers

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

Offline

#11 December 30 2017

varbha
Member

Re: [Exercise] Similar Integers

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

Offline

Board footer