Knowee
Questions
Features
Study Tools

Given an array, you have to find the ceil of a number x. The ceil of a number x is nothing but the smallest number in the array greater than or equal to x.Input FormatThe first line of input contains the N-size of the array. The next line contains N integers, the elements of the array. The next line contains Q - number of queries. Each of the next Q lines contains a single integer X, for which you have to find the ceil of X in the given array.Output FormatFor each query, print the ceil of X, separated by a new line. If ceil is not found, print the value of "INT_MAXConstraints30 points1 <= N <=1051 <= Q <=102-108 <= ar[i] <=10870 points1 <= N <=1051 <= Q <=105-108 <= ar[i] <=108

Question

Given an array, you have to find the ceil of a number x. The ceil of a number x is nothing but the smallest number in the array greater than or equal to x.Input FormatThe first line of input contains the N-size of the array. The next line contains N integers, the elements of the array. The next line contains Q - number of queries. Each of the next Q lines contains a single integer X, for which you have to find the ceil of X in the given array.Output FormatFor each query, print the ceil of X, separated by a new line. If ceil is not found, print the value of "INT_MAXConstraints30 points1 <= N <=1051 <= Q <=102-108 <= ar[i] <=10870 points1 <= N <=1051 <= Q <=105-108 <= ar[i] <=108

...expand
🧐 Not the exact question you are looking for?Go ask a question

Solution 1

The problem is asking to find the smallest number in the array that is greater than or equal to a given number. Here are the steps to solve this problem:

  1. Read the size of the array (N) from the input.
  2. Read the elements of the array.
  3. Sort the array in ascending order.
  4. Read the number of queries (Q) from the input.
  5. For each query, do the following:
    • Read the number (X) from the input.
    • Use binary search to find the smallest number in the array that is greater than or equal to X. If such a number is found, print it. If not, print "INT_MAX".

Here is a Python solution for the problem:

import bisect

# Read the size of the array
N = int(input().strip())

# Read the elements of the array
arr = list(map(int, input().strip().split()))

# Sort the array
arr.sort()

# Read the number of queries
Q = int(input().strip())

# For each query
for _ in range(Q):
    # Read the number
    X = int(input().strip())
    
    # Find the ceil of X in the array
    idx = bisect.bisect_left(arr, X)
    
    # If the ceil is found
    if idx != len(arr):
        print(arr[idx])
    else:
        print("INT_MAX")

This solution uses the bisect_left function from the bisect module to perform binary search. The function returns the insertion point for X in arr to maintain sorted order. If X is already present in arr, the insertion point is before (to the left of) any existing entries. The returned insertion point idx is the index of the smallest element that is greater than or equal to X. If all elements in the array are less than X, the function returns len(arr).

This problem has been solved

Solution 2

The problem is asking to find the smallest number in the array that is greater than or equal to a given number. Here are the steps to solve this problem:

  1. Read the size of the array (N) from the input.
  2. Read the elements of the array.
  3. Sort the array in ascending order.
  4. Read the number of queries (Q) from the input.
  5. For each query:
    • Read the number (X) from the input.
    • Use binary search to find the smallest number in the array that is greater than or equal to X. If such a number is found, print it. If not, print "INT_MAX".

Here is a Python solution for the problem:

import bisect

# Read the size of the array
N = int(input().strip())

# Read the elements of the array
arr = list(map(int, input().strip().split()))

# Sort the array
arr.sort()

# Read the number of queries
Q = int(input().strip())

# Process each query
for _ in range(Q):
    # Read the number
    X = int(input().strip())
    
    # Find the ceil of X in the array
    index = bisect.bisect_left(arr, X)
    
    # Print the result
    if index != len(arr):
        print(arr[index])
    else:
        print("INT_MAX")

This solution uses the bisect_left function from the bisect module to perform a binary search in the sorted array. The function returns the insertion point for X in arr to maintain sorted order. If X is already present in arr, the insertion point is before (to the left of) any existing entries. The returned index i partitions the array arr into two halves so that all(val < X for val in arr[:i]) and all(val >= X for val in arr[i:]).

This problem has been solved

Similar Questions

Given an array, you have to find the floor of a number x. The floor of a number x is nothing but the largest number in the array less than or equal to x.Input FormatThe first line of input contains the N - the size of the array. The next line contains N integers, the elements of the array. The next line contains Q - number of queries. Each of the next Q lines contains a single integer X, for which you have to find the floor of X in the given array.Output FormatFor each query, print the floor of X, separated by a new line. If the floor is not found, print the value of "INT_MIN".Constraints30 points1 <= N <= 1051 <= Q <= 102-108 <= ar[i] <= 10870 points1 <= N <= 1051 <= Q <= 105-108 <= ar[i] <= 108ExampleInput6-6 10 -1 20 15 55-1108-10-4Output-1105-2147483648-6

Given an array, you have to find the frequency of a number x.Input FormatThe first line of input contains N - size of the array. The next line contains N integers, the elements of the array. The next line contains Q - number of queries. Each of the next Q lines contains a single integer X, for which you have to find the frequency of X in the given array.Output FormatFor each query, print the frequency of X, separated by a new line.Constraints20 points1 <= N <= 1051 <= Q <= 102-108 <= ar[i] <= 10830 points1 <= N <= 1051 <= Q <= 105-108 <= ar[i] <= 10850 points1 <= N <= 1051 <= Q <= 105-108 <= ar[i] <= 108ExampleInput9-6 10 -1 20 -1 15 5 -1 155-11081520Output31021

We use the integers , , and to create the following series:You are given queries in the form of , , and . For each query, print the series corresponding to the given , , and values as a single line of space-separated integers.Input FormatThe first line contains an integer, , denoting the number of queries.Each line of the subsequent lines contains three space-separated integers describing the respective , , and values for that query.ConstraintsOutput FormatFor each query, print the corresponding series on a new line. Each series must be printed in order as a single line of space-separated integers.Sample Input20 2 105 3 5Sample Output2 6 14 30 62 126 254 510 1022 20468 14 26 50 98ExplanationWe have two queries:We use , , and to produce some series :... and so on.Once we hit , we print the first ten terms as a single line of space-separated integers.We use , , and to produce some series :We then print each element of our series as a single line of space-separated values.

You are given an integer array nums, an integer array queries, and an integer x.For each queries[i], you need to find the index of the queries[i]th occurrence of x in the nums array. If there are fewer than queries[i] occurrences of x, the answer should be -1 for that query.Return an integer array answer containing the answers to all queries. Example 1:Input: nums = [1,3,1,7], queries = [1,3,2,4], x = 1Output: [0,-1,2,-1]Explanation:For the 1st query, the first occurrence of 1 is at index 0.For the 2nd query, there are only two occurrences of 1 in nums, so the answer is -1.For the 3rd query, the second occurrence of 1 is at index 2.For the 4th query, there are only two occurrences of 1 in nums, so the answer is -1.Example 2:Input: nums = [1,2,3], queries = [10], x = 5Output: [-1]Explanation:For the 1st query, 5 doesn't exist in nums, so the answer is -1. Constraints:1 <= nums.length, queries.length <= 1051 <= queries[i] <= 1051 <= nums[i], x <= 104

arrayfindProblem DescriptionRar the cat hates counting and wants you to help. This time, he has an array of numbers not more than 1000000 length long. He also has Q queries. Each query will consist of a number, x. You are supposed to tell him how many numbers in the array are above and below x.InputThe first line of input consists of L, the length of the array.The second line of input consists of L integers, space separated. You may assume they all fit into a 32bit signed integer.The third line of input consists of Q, the number of queries. Q will be not more than 10000.The following Q line of input consists of one number each, x. You may assume they all fit into a 32bit signed integer.OutputFor each query, output how many numbers is smaller than it and how many numbers are greater than it (See Below).Sample Input105 8 7 2 4 3 7 9 1 957010036Sample OutputSmaller: 5, Greater: 3Smaller: 0, Greater: 10Smaller: 10, Greater: 0Smaller: 2, Greater: 7Smaller: 5, Greater: 5

1/2

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.