Let a pair of distinct positive integers, (i, j), be considered “scrambled” if you can obtain j by reordering the digits of i. For example, (12345, 25341) is a scrambled pair, but (12345, 67890) is not.

Given integers A and B with the same number of digits and no leading zeroes, how many distinct scrambled pairs (i, j) are there that satisfy: A <= i < j <= B?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Scramble{
	
    /**
    * Calculate the number of distinct scrambled pairs within the given range
    * @param min, the minimum value
    * @param max, the maximum value 
    * @return the number of distinct scrambled pairs within the given range
    */
    public static long scrambleCalculator(int min, int max){
        // make sure min is actually smaller than max
        if (min >= max){return 0;}
		
        // cache for visited scramble integers in the range to avoid duplicate
        Set<Integer> cache = new HashSet<Integer>();
		
        // initialize total scrambled pair count
        long count = 0;
		
        // for each integer in the range:
        for (int i = min; i <= max; i++){
            // if this integer is not in the cache, then we haven't calculated
            // the number of its scrambled pairs:
            if (!cache.contains(i)){
				
            //convert to digits
            List<Integer> digits = intToDigits(i);
				
            //compute permutation for this combination of digits
            Set<Integer> res = new HashSet<Integer>();
            permutation(res, digits, min, max, 0, 0, digits.size());
				
            // compute pair count and update total count
            count += countPairs((long) res.size());
				
            // add permutations into the cache
            if (res.size() > 1){
                cache.addAll(res);
            }
        }
    }
    return count;
    }
	
    /**
    * Recursively visit the digits combination and get the permutations of the given
    *  digits combination within the range. For example, if the digits are [1,2,3], 
    *  then we get the following permutations in order: 123, 132, 213, 231, 312, 321,
    *  assuming the range is from 100 to 999.
    * @param total, a set to store the permutations that meet the requirements
    * @param digits, a list of digits of the original number
    * @param min, the minimum value
    * @param max, the maximum value
    * @param value, a permutation of the given digits when it reaches the length of the original integer
    * @param pos, the number of digits we have "built" for a permutation
    * @param length, the number of digits in the original integer
    */
    public static void permutation(Set<Integer> total, List<Integer> digits, int min, int max, int value, int pos, int length){
        // we have "rebuilt" a new integer with the same number of digits
        if (pos == length){
            // make sure it's within the range
            if (min <= value && value <= max){
                total.add(value);
            }
            return;
        }
		
        for (int i = 0; i < digits.size(); i++){
            // avoid leading zero
            if (value != 0 || digits.get(i) != 0){
                value = value * 10 + digits.get(i);
                digits.remove(i);
                permutation(total, digits, min, max, value, pos + 1, length);
                digits.add(i, value % 10);
                value /= 10;
            }
        }
    }
	
    /**
    * Compute the count of distinct pairs of elements in a set
    * @param size, total number of elements in a set
    * @return count of distinct pairs of elements
    */
    public static long countPairs(Long size){
        // make sure there is at least one pair
        if (size < 2){return 0;}
		
        // assume we have n elements in an array, then for the first element, it can
        // form (n-1) pairs with the elements on its right; for the second 
        // element, it can form (n-2) pairs with the elements on its right without
        // duplicated pairs from the previous step..... then for the last two 
        // element, it can form 1 pair with the last one element, and for the last
        // element, it can form 0 pair. Thus, the total number of distinct pairs is
        // (0 + n - 1) * n / 2
        return (0 + size - 1) * size /2;
    }
	
	
    /**
    * Convert a positive integer to a list of digits in the integer. For
    * example, if the integer is 115, the method will return [5,1,1]
    * @param num, a positive integer.
    * @return a list of digits in the integer in reversed order
    */
    public static List<Integer> intToDigits(Integer num){
        List<Integer> ints = new ArrayList<Integer>();
        if (num == null || num < 0){return ints;}
		
        // process from the last digit to the first digit
        while (num > 0){
            int last = num % 10;
            ints.add(last);
            num /= 10;
        }
		
        return ints;
    }
	
    public static void main(String[] args){
        int min = 10000000;
        int max = 25000000;
		
        long total = scrambleCalculator(min,max);
        System.out.println(total);
    }
}