Week 1 - Assignment 2 - CS103 - Swayam

Week 1 - Assignment 2

Problem Statement

There is a photo-shoot going on at your school, and you are tasked to organize the photo-shoot. However, there is not much space in your campus for everyone to stand side by side for the group photo. You come up with the idea of making everyone stand in a queue and taking their photo from one side of the queue. There are n students in your class, and all are standing randomly in a queue for the photo. You are given the height of each of the students as an array of integers H where Hi is the height of the ith student in the queue from the left. Find out which side of the queue you should take the photo from so that everyone is visible.

Photo Shoot Image from Swayam
Figure: Image Taken from Swayam MOOC Course 'Getting Started with Competitive Programming'. All copyrights reserved with Swayam

In the above configuration, taking the photo from the left would be ideal so that everyone is captured and covered by the person in front. If the image was taken from the right then only the rightmost student would be visible.

Input Format

The first line of the input contains a single integer t which is the number of test cases. t test cases follow.

Each test case has two lines of input.

Constraints

1 < t < 100

1 < n < 105

1 < Hi < 1015

Output Format

A single line of output for each test case, containing the string "L" if the best position to take the photo is the left of the queue, and "R" if the best position to take the photo is the right side. It should print "N" if neither position works. If both Left and Right works, output "L".

Sample Input 1

Input:
1
5
1 2 3 4 5

Output:

L

Explanation

If we capture from the left, everyone will be visible, but if we capture from the right then only the rightmost person will be visible.

Solution

def is_ascending(arr):
    # Check if the array is in ascending order
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True

def is_descending(arr):
    # Check if the array is in descending order
    for i in range(len(arr) - 1):
        if arr[i] < arr[i + 1]:
            return False
    return True

def main():
    # Read the number of test cases
    t = int(input())
    for _ in range(t):
        # Read the size of the array (not used in this logic)
        n = int(input())
        # Read the array elements
        h = list(map(int, input().split()))

        # Check the order of the array and print the corresponding result
        if is_ascending(h):
            print("L")  # Array is in ascending order
        elif is_descending(h):
            print("R")  # Array is in descending order
        else:
            print("N")  # Array is neither in ascending nor descending order

# Ensure the main function runs only when the script is executed directly
if __name__ == "__main__":
    main()

Sample Solution Provided by Instructor

def solve(nums, n):
    # If the array has only one element, it is considered to be sorted in a single direction (either increasing or decreasing)
    # by definition, so we return "L" (likely representing "Left" or "Increasing").
    if n == 1: 
        return "L"
    
    # We start by assuming the array is both increasing and decreasing.
    is_inc = True  # Flag to track if the array is increasing
    is_dec = True  # Flag to track if the array is decreasing
    
    # Iterate over the array from the second element to the end.
    for i in range(1, n):
        # If at any point, the array is neither increasing nor decreasing, return "N" (likely meaning "Neither").
        if not is_inc and not is_dec:
            return "N"
        
        # If the current element is smaller than the previous one, the array can't be increasing.
        if nums[i] < nums[i-1]:
            is_inc = False
        
        # If the current element is larger than the previous one, the array can't be decreasing.
        if nums[i] > nums[i-1]:
            is_dec = False
    
    # After the loop, check the flags:
    # If the array was always increasing, return "L".
    if is_inc:
        return "L"
    
    # If the array was always decreasing, return "R" (likely representing "Right" or "Decreasing").
    if is_dec:
        return "R"

# Read the number of test cases.
t = int(input())

# Loop through each test case.
for _ in range(t):
    # Read the size of the array.
    n = int(input())
    
    # Read the array elements and convert them into a list of integers.
    nums = list(map(int, input().split()))
    
    # Call the solve function and print the result for the current test case.
    print(solve(nums, n))