Leetcode 2376 Node With Highest Edge Score Solution in Java | Hindi Coding Community

 

We call a positive integer special if all of its digits are distinct.

Given a positive integer n, return the number of special integers that belong to the interval [1, n].

 

Example 1:

Input: n = 20
Output: 19
Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.

Example 2:

Input: n = 5
Output: 5
Explanation: All the integers from 1 to 5 are special.

Example 3:

Input: n = 135
Output: 110
Explanation: There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.

 

Constraints:

• 1 <= n <= 2 * 109

Java Code :

public int countSpecialNumbers(int N) {

// Transform N + 1 to arrayList

ArrayList<Integer> L = new ArrayList<Integer>();

for (int x = N + 1; x > 0; x /= 10)

L.add(0, x % 10);

// Count the number with digits < N

int res = 0, n = L.size();

for (int i = 1; i < n; ++i)

res += 9 * A(9, i - 1);

// Count the number with same prefix

HashSet<Integer> seen = new HashSet<>();

for (int i = 0; i < n; ++i) {

for (int j = i > 0 ? 0 : 1; j < L.get(i); ++j)

if (!seen.contains(j))

res += A(9 - i, n - i - 1);

if (seen.contains(L.get(i))) break;

seen.add(L.get(i));

}

return res;

}

public int A(int m, int n) {

return n == 0 ? 1 : A(m, n - 1) * (m - n + 1);

}