Fixed Point

Problem

Given an array of distinct integers arr, where arr is sorted in ascending order, return the smallest index i that satisfies arr[i] == i. If there is no such index, return -1.

Follow up: The O(n) solution is very straightforward. Can we do better?

Constraints

• 1 <= arr.length < 104
• -109 <= arr[i] <= 109

Solution

The problem Fixed Point can be solved using a binary search as the given array is sorted in ascending order.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    bool confusingNumber(int n)
    {
        int rotate = 0;
        string num = to_string(n);

        for (int i = num.length(); i > 0; i--)
        {
            rotate *= 10;
            if (num[i - 1] == '0' || num[i - 1] == '1' || num[i - 1] == '8')
                rotate += num[i - 1] - '0';
            else if (num[i - 1] == '6')
                rotate += 9;
            else if (num[i - 1] == '9')
                rotate += 6;
            else
                return false;
        }

        return n != rotate;
    }
};