Solution Explanation

This problem asks to determine if a number is a "confusing number". A confusing number is one that, when rotated 180 degrees, becomes a different valid number. Only the digits 0, 1, 6, 8, and 9 remain valid after rotation (becoming 0, 1, 9, 8, and 6 respectively). Other digits become invalid.

The solution uses a straightforward approach:

1. Rotation Mapping: A lookup array d maps each digit to its rotated equivalent. Invalid digits are represented by -1. For example, d[6] = 9 and d[2] = -1.

2. Iterative Rotation: The code iterates through the digits of the input number n. For each digit:

   • It checks if the digit is valid (not -1 in the d array). If not, the number is not confusing, and false is returned immediately.
   • It calculates the rotated number y by appending the rotated digit (from d) to the beginning of y. This effectively reverses and transforms the number.

3. Comparison: After processing all digits, the code compares the original number n with the rotated number y. If they are different, n is a confusing number, and true is returned; otherwise, false is returned.

Time and Space Complexity Analysis

Time Complexity: O(log₁₀ n). The while loop iterates through the digits of the number n. The number of digits is proportional to the logarithm base 10 of n.

Space Complexity: O(1). The space used by the d array and the variables x and y is constant and does not depend on the input size. It's constant space.

Code in Different Languages

The provided code demonstrates the solution in Python, Java, C++, Go, and PHP. All versions follow the same algorithm:

Python3:

class Solution:
    def confusingNumber(self, n: int) -> bool:
        x, y = n, 0
        d = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
        while x:
            x, v = divmod(x, 10)
            if d[v] < 0:
                return False
            y = y * 10 + d[v]
        return y != n

Java:

class Solution {
    public boolean confusingNumber(int n) {
        int[] d = new int[] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        int x = n, y = 0;
        while (x > 0) {
            int v = x % 10;
            if (d[v] < 0) {
                return false;
            }
            y = y * 10 + d[v];
            x /= 10;
        }
        return y != n;
    }
}

C++:

class Solution {
public:
    bool confusingNumber(int n) {
        vector<int> d = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
        int x = n, y = 0;
        while (x) {
            int v = x % 10;
            if (d[v] < 0) {
                return false;
            }
            y = y * 10 + d[v];
            x /= 10;
        }
        return y != n;
    }
};

Go:

func confusingNumber(n int) bool {
	d := []int{0, 1, -1, -1, -1, -1, 9, -1, 8, 6}
	x, y := n, 0
	for x > 0 {
		v := x % 10
		if d[v] < 0 {
			return false
		}
		y = y*10 + d[v]
		x /= 10
	}
	return y != n
}

PHP:

class Solution {
    /**
     * @param Integer $n
     * @return Boolean
     */
    function confusingNumber($n) {
        $d = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6];
        $x = $n;
        $y = 0;
        while ($x > 0) {
            $v = $x % 10;
            if ($d[$v] < 0) {
                return false;
            }
            $y = $y * 10 + $d[$v];
            $x = intval($x / 10);
        }
        return $y != $n;
    }
}

All these code snippets implement the same efficient algorithm with a constant space complexity and logarithmic time complexity. The choice of language primarily affects syntax and minor details.