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)
       {
           list.add(0,temp%10);
           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;
           set.add(list.get(i));
       }
       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;
    }
}


221 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.