medium
1 views

Check Sorted Order

Given an array sorted except for one element, find the first element that when reversed makes the entire array sorted

Understand the Problem

Problem Statement

The program must accept N integers which are sorted in ascending order except one integer. But if that single integer R is reversed, the entire array will be in sorted order. The program must print the first integer that must be reversed so that the entire array will be sorted in ascending order.

Constraints

  • 2 <= N <= 20
  • All integers in the array are positive
  • Exactly one integer needs to be reversed to make the array sorted
  • The reversed integer must result in a valid positive number
  • The array contains no duplicates

Examples

Example 1
Input
5
10 71 20 30 33
Output
71
Explanation

When 71 is reversed to 17, the array becomes [10, 17, 20, 30, 33] which is sorted in ascending order.

Example 2
Input
6
10 20 30 33 64 58
Output
64
Explanation

When 64 is reversed to 46, the array becomes [10, 20, 30, 33, 46, 58] which is sorted in ascending order.

Example 3
Input
6
10 20 30 33 67 58
Output
58
Explanation

When 58 is reversed to 85, the array becomes [10, 20, 30, 33, 67, 85] which is sorted in ascending order.

Solution

#include <stdio.h>

int reverseNumber(int n) {
    int reve = 0;
    while (n > 0) {
        int r = n % 10;
        reve = reve * 10 + r;
        n = n / 10;
    }
    return reve;
}

int isSorted(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    for (int i = 0; i < n; i++) {
        int original = arr[i];
        arr[i] = reverseNumber(original);
        
        if (isSorted(arr, n)) {
            printf("%d", original);
            break;
        }
        
        arr[i] = original;
    }
    
    return 0;
}
Time:O(N²) - We check at most N elements, and for each check we verify if the array is sorted which takes O(N) time
Space:O(N) - We store the array of N elements
Approach:

C Solution Explanation:

  1. reverseNumber(): Reverses the digits of a number by extracting each digit using modulo and division operations
  2. isSorted(): Checks if an array is sorted in ascending order by comparing adjacent elements
  3. main():
    • Reads N and the array elements
    • Iterates through each element from left to right
    • For each element, stores original value, replaces it with reversed version, and checks if array is sorted
    • If sorted, prints the original element and exits
    • Otherwise, restores the original element and continues

Visual Explanation

Loading diagram...
All Problems