Welcome to Subscribe On Youtube

788. Rotated Digits

Description

An integer x is a good 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. For example:

  • 0, 1, and 8 rotate to themselves,
  • 2 and 5 rotate to each other (in this case they are rotated in a different direction, in other words, 2 or 5 gets mirrored),
  • 6 and 9 rotate to each other, and
  • the rest of the numbers do not rotate to any other number and become invalid.

Given an integer n, return the number of good integers in the range [1, n].

 

Example 1:

Input: n = 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.

Example 2:

Input: n = 1
Output: 0

Example 3:

Input: n = 2
Output: 1

 

Constraints:

  • 1 <= n <= 104

Solutions

  • class Solution {
        private int[] a = new int[6];
        private int[][] dp = new int[6][2];
    
        public int rotatedDigits(int n) {
            int len = 0;
            for (var e : dp) {
                Arrays.fill(e, -1);
            }
            while (n > 0) {
                a[++len] = n % 10;
                n /= 10;
            }
            return dfs(len, 0, true);
        }
    
        private int dfs(int pos, int ok, boolean limit) {
            if (pos <= 0) {
                return ok;
            }
            if (!limit && dp[pos][ok] != -1) {
                return dp[pos][ok];
            }
            int up = limit ? a[pos] : 9;
            int ans = 0;
            for (int i = 0; i <= up; ++i) {
                if (i == 0 || i == 1 || i == 8) {
                    ans += dfs(pos - 1, ok, limit && i == up);
                }
                if (i == 2 || i == 5 || i == 6 || i == 9) {
                    ans += dfs(pos - 1, 1, limit && i == up);
                }
            }
            if (!limit) {
                dp[pos][ok] = ans;
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        int a[6];
        int dp[6][2];
    
        int rotatedDigits(int n) {
            memset(dp, -1, sizeof dp);
            int len = 0;
            while (n) {
                a[++len] = n % 10;
                n /= 10;
            }
            return dfs(len, 0, true);
        }
    
        int dfs(int pos, int ok, bool limit) {
            if (pos <= 0) {
                return ok;
            }
            if (!limit && dp[pos][ok] != -1) {
                return dp[pos][ok];
            }
            int up = limit ? a[pos] : 9;
            int ans = 0;
            for (int i = 0; i <= up; ++i) {
                if (i == 0 || i == 1 || i == 8) {
                    ans += dfs(pos - 1, ok, limit && i == up);
                }
                if (i == 2 || i == 5 || i == 6 || i == 9) {
                    ans += dfs(pos - 1, 1, limit && i == up);
                }
            }
            if (!limit) {
                dp[pos][ok] = ans;
            }
            return ans;
        }
    };
    
  • class Solution:
        def rotatedDigits(self, n: int) -> int:
            @cache
            def dfs(pos, ok, limit):
                if pos <= 0:
                    return ok
                up = a[pos] if limit else 9
                ans = 0
                for i in range(up + 1):
                    if i in (0, 1, 8):
                        ans += dfs(pos - 1, ok, limit and i == up)
                    if i in (2, 5, 6, 9):
                        ans += dfs(pos - 1, 1, limit and i == up)
                return ans
    
            a = [0] * 6
            l = 1
            while n:
                a[l] = n % 10
                n //= 10
                l += 1
            return dfs(l, 0, True)
    
    
  • func rotatedDigits(n int) int {
    	a := make([]int, 6)
    	dp := make([][2]int, 6)
    	for i := range a {
    		dp[i] = [2]int{-1, -1}
    	}
    	l := 0
    	for n > 0 {
    		l++
    		a[l] = n % 10
    		n /= 10
    	}
    
    	var dfs func(int, int, bool) int
    	dfs = func(pos, ok int, limit bool) int {
    		if pos <= 0 {
    			return ok
    		}
    		if !limit && dp[pos][ok] != -1 {
    			return dp[pos][ok]
    		}
    		up := 9
    		if limit {
    			up = a[pos]
    		}
    		ans := 0
    		for i := 0; i <= up; i++ {
    			if i == 0 || i == 1 || i == 8 {
    				ans += dfs(pos-1, ok, limit && i == up)
    			}
    			if i == 2 || i == 5 || i == 6 || i == 9 {
    				ans += dfs(pos-1, 1, limit && i == up)
    			}
    		}
    		if !limit {
    			dp[pos][ok] = ans
    		}
    		return ans
    	}
    
    	return dfs(l, 0, true)
    }
    

All Problems

All Solutions