CODEWITHSUNDEEP
python
casillas
casillas

Reputation: 16793

Rotated Digits in Python

I have came across to the following question, my solution passed the initial input, but failed in the following test case. I wonder what I am missing.

The question is described as follows

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:

Input: 10

Output: 4

Explanation:

There are four good numbers in the range [1, 10] : 2, 5, 6, 9. Note that 1 and 10 are not good numbers, since they remain unchanged after rotating. 

class Solution(object):
    def rotatedDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        rotatedDigits = [2,5,6,9]
        count = 0
        isValid = False
        for i in range(1,N+1):
                for b in str(i):
                    if int(b) in rotatedDigits:
                        isValid = True
                    else:
                        isValid = False
                        break
                if isValid:
                    count +=1
        return count

Input: 857

Output: 68

Expected: 247

Upvotes: 3

Views: 2474

Answers (5)

prajwal
prajwal

Reputation: 1

first, make a list of number[coverted number to string] in d_l then check bad_numbers is present or not then check that d_l is a subset of only valid numbers or not then if any number pass all the conditions it means it's a good number.

def rotatedDigits(self, N: int) -> int:
        count = 0
        for d in range(1, N+1):
            d_l = [ch for ch in str(d)]
            if '3' in d_l or '4' in d_l or '7' in d_l:
                continue   
            if set(d_l).issubset({'0', '1', '8'}):
                continue    
            count += 1
        return count

Upvotes: 0

Manish
Manish

Reputation: 521

# using dictionary :

def rotatedDigits(N: int):
    count=0
    d={0:0,1:1,2:5,3:-1,4:-1,5:2,6:9,7:-1,8:8,9:6}
    for i in range(1,N+1):
        l=list(str(i))
        res=[]
        for j in l:
            if d[int(j)]!=-1:
                res.append(str(d[int(j)]))
            else:break
        if len(res)==len(l) and int(''.join(res))!=i:
            count+=1
    return count

Upvotes: 0

Alan Hoover
Alan Hoover

Reputation: 1440

I would take a different approach by first checking for any of the invalid characters. Then verify that it does contain at least one of the rotating characters.

rotating = {'2','5','6','9'}
invalid = {'3','4','7'}

def rotated(N):
    X=set(str(N))
    if any(digit in X for digit in invalid):
        return False
    if any(digit in X for digit in rotating):
        return True
    return False

def checkall(N):
    count=0
    for i in range(1,N+1):
        if rotated(i): 
            count += 1
    return count

print(checkall(857))

Upvotes: 1

pault
pault

Reputation: 43494

Your logic is incomplete. You are checking for the presence of the digits that rotate, which is correct. But the problem statement also says:

"the rest of the numbers do not rotate to any other number and become invalid"

Thus if the number contains any of the numbers 3, 4, or 7 it is invalid.

Even if you were to add in that check, your isValid flag is in the wrong place. It should be reset inside the for loop (not set outside of it).

Here's a version of your function that will work:

def rotatedDigits(N):
    """
    :type N: int
    :rtype: int
    """
    rotatedDigits = {'2','5','6','9'}
    badNumbers = {'3','4','7'}
    count = 0
    for i in range(1,N+1):
        flag1 = False  # use this to check if the number contains a rotating digit
        flag2 = True  # use this to check if the number contains a bad digit
        for b in str(i):
            if b in rotatedDigits:
                flag1 = True
            elif b in badNumbers:
                flag2 = False
                break

        if flag1 and flag2:
            count +=1
    return count

print(rotatedDigits(857))
#247

I also made made rotatedDigits and badNumbers sets of strings instead of lists of ints. Set lookups are faster than lists, and also this avoids casting to string and back to int.

Update: A more pythonic version using set operations:

def rotatedDigits(N):
    """
    :type N: int
    :rtype: int
    """
    rotatedDigits = {'2','5','6','9'}
    badNumbers = {'3','4','7'}
    count = 0
    for i in range(1,N+1):
        digits = set(str(i))
        count += 1 if (digits & rotatedDigits) and not(digits & badNumbers) else 0
    return count

Here we create a set of the characters in the number (digits) and use the & operator between sets to get the intersection. We increment count if the intersection between digits and rotatedDigits is not empty and the intersection of digits and badNumbers is empty.

The above function can be further condensed using sum, map, and a generator expression:

def rotatedDigits(N):
    """
    :type N: int
    :rtype: int
    """
    rotatedDigits = {'2','5','6','9'}
    badNumbers = {'3','4','7'}
    count = sum(1 if (x & rotatedDigits) and not (x & badNumbers) else 0 
                for x in map(lambda i: set(str(i)), range(1, N+1)))
    return count

Upvotes: 3

Nikolay Tsvetanov
Nikolay Tsvetanov

Reputation: 94

Whit this check

if int(b) in rotatedDigits:
    isValid = True
else:
    isValid = False
    break

You have missed numbers with digits: 0, 1, and 8. In given example they represented numbers that stay the same but they are valid You must miss all numbers with digits 3, 4 or 7.

Upvotes: 0

Related Questions