CODEWITHSUNDEEP
algorithmmathnumber-theory
akhil
akhil

Reputation: 1883

Counting distinct digits

Is there any efficient way to find out the count of distinct digits from a given number in constant time or O(Logn)?

Suppose n = 1234 the count should be 4 (As there are 4 distinct digits)

if n = 1121 the count should be 2 (As there are 2distinct digits i.e 1, 2)

Constraint: 0 <= n <= 1000000007

Upvotes: 1

Views: 993

Answers (3)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

Since the numbers are (relatively) small, we can just convert these to a string, pass these through a uniqness filter, and calculate the number of elements. For example in Python:

def nuniqdigits(n):
    return len(set(str(n)))

Converting to a string is relatively expensive, we can iteratevly enumerate the digits as follows:

def digits(n):
    if n:
        while n:
            yield n % 10
            n //= 10
    else:
        yield 0

so then we can calculate the number of distinct digits as:

def nuniqdigits(n):
    return len(set(digits(n)))

Since the possible values for digits is limited, we can use a bitmask here. For example in Haskell:

import Data.Bits((.|.), popCount, shiftL)
import Data.Word(Word16)

nuniqdigits :: Int -> Int
nuniqdigits n = popCount (foldr (.|.) (0 :: Word16) (map (shiftL 1) (digits n)))
    where digits n | n <= 9 = [n]
                   | otherwise = uncurry (flip (:) . digits) (divMod n 10)

A number n has O(log n) digits, and since we make iterations in the number of digits, and all operations are constant in each iteration, this runs in O(log n).

Upvotes: 1

500 - Internal Server Error
500 - Internal Server Error

Reputation: 28829

Pseudo-code:

int DistinctDigits(int n)
{
    int result = 0;
    bool[10] digitFound = {false};

    while (n > 0)
    {
      d = n % 10;
      n = n / 10;

      if (!digitFound[d])
      {
        result++;
        digitFound[d] = true;
      }
    }
    return result;
}

Note that you have to think about what to do with leading zeroes (including when n == 0).

Upvotes: 2

Nakul Bharti
Nakul Bharti

Reputation: 111

use map with key as digit and value as it's count. now the size of the map will be your answer. or use set, since set does not contain a duplicate element size of the set will be your answer

Upvotes: 3

Related Questions