Solution 1 for Scaler Topics Fortnightly Contest - 25
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Tile Square Problem
This article is part of the Scaler Topics Fortnightly Contest - 25
Solution Approach
When there are no tiles initially on the wall, placing one tile on any block suffices to begin forming a square pattern. In the scenario where tiles already exist on the wall, the following steps are taken to determine the required calculations:
Identify Four Values:
- minX: The index of the upper row with a tile.
- maxX: The index of the bottom row with a tile.
- minY: The index of the leftmost column with a tile.
- maxY: The index of the rightmost column with a tile.
Subsequently, we derive the length of the square side needed after attaching tiles. Let this side be denoted as ‘len.’ The value of ‘len’ is determined as follows: len = max(maxX − minX + 1, maxY − minY + 1). A solution isn’t feasible if ‘len’ exceeds either N (the wall’s length) or M (the wall’s width). Otherwise, the answer is calculated as len × len − cnt, where len × len represents the number of cells in the resulting square, and ‘cnt’ represents the number of tiles initially present on the wall.
Time Complexity: O(N * M) Space Complexity: O(N * M)
C++ Implementation
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more
