Find a Length-3 Battleship in an N×N Grid Using a Hit/Miss API

Problem: Find a Length-3 Battleship in an N×N Grid Using a Hit/Miss API You are given a square grid of size N × N with N >= 3. Grid coordinates are represented as (x, y) where 0 <= x, y < N. A single battleship of length 3 is hidden in the grid: It is placed either horizontally or vertically (never diagonally). The 3 occupied cells are contiguous. All other cells are empty. You can query the grid only via the following API: bomb_location(x, y) -> bool Returns True if (x, y) is part of the battleship (a hit) Returns False otherwise (a miss) Task Implement: find_battleship(N) -> ((x1,y1), (x2,y2), (x3,y3)) Return the three coordinates occupied by the battleship (order does not matter, but the set must be correct). Example For N = 8, if the battleship occupies: (1,2), (2,2), (3,2) (vertical) then find_battleship(8) should return those three coordinates in any order. Constraints / Notes You must rely only on bomb_location to gather information. Discuss the number of API calls (worst-case complexity). Test Cases (Conceptual) Since bomb_location is an interactive/black-box API, the following describe the hidden ship positions and expected output sets. N=3, horizontal: {(0,0),(0,1),(0,2)} → output that set N=3, vertical: {(0,1),(1,1),(2,1)} → output that set N=5, horizontal: {(4,1),(4,2),(4,3)} → output that set N=8, vertical: {(1,2),(2,2),(3,2)} → output that set N=10, vertical on boundary: {(7,9),(8,9),(9,9)} → output that set Example Input N=3, hidden ship={(0,0),(0,1),(0,2)} Output Return those 3 coordinates in any order