top of page
Search

# Numbers With Repeated Digits

Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.

Example 1:

```Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.
```

Example 2:

```Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
```

Example 3:

```Input: 1000
Output: 262```

Note: 1 <= N <= 10^9

Solution:

```class Solution {
public int numDupDigitsAtMostN(int N) {
List<Integer>list = new ArrayList<>();
int count=0;

int temp=N+1;
while(temp!=0)
{
temp=temp/10;
}

for(int i=0;i<list.size()-1;i++)
{
count+=9*permutation(9,i);
}

Set<Integer> set = new HashSet<>();
for(int i=0;i<list.size();i++)
{
for(int j= i==0?1:0;j<list.get(i);j++)
{
if(set.contains(j)) continue;
else count+=permutation(10-(i+1),list.size()-1-i);
}
if(set.contains(list.get(i))) break;
}
return N-count;
}

private int permutation(int n,int r)
{
int nonrepeatingnos = 1;
for(int i=0;i<r;i++)
{
nonrepeatingnos*=n;
n--;
}
return nonrepeatingnos;
}
}
```