Minimum Cost to Tile a Strip with Widths 1, 2, and 3
Updated
Problem statement
You need to cover a strip of n cells, placed in a row, with tiles. There are three kinds of tiles: a tile of width 1 covers one cell, a tile of width 2 covers two neighboring cells, and a tile of width 3 covers three neighboring cells. You have as many tiles of each kind as you want.
One tile of width 1 costs cost[0], one tile of width 2 costs cost[1], and one tile of width 3 costs cost[2].
Every cell must be covered by exactly one tile, and no tile may stick out past the end of the strip. Return the smallest total cost to cover the whole strip.
Function
minTilingCost(n: int, cost: int[]) → longExamples
Example 1
n = 4cost = [10,3,4]return = 6Use two tiles of width 2: 3 + 3 = 6. The width 3 tile is the cheapest per cell, but after it one cell is left, and a width 1 tile costs 10, so that plan costs 4 + 10 = 14.
Example 2
n = 5cost = [2,5,5]return = 9Use one tile of width 3 and two tiles of width 1: 5 + 2 + 2 = 9. Five width 1 tiles cost 10, and a width 3 tile plus a width 2 tile also cost 10.
Example 3
n = 1cost = [7,1,1]return = 7The strip has one cell. The wider tiles are cheaper, but they would stick out past the end, so the only choice is one width 1 tile for 7.
Constraints
1 <= n <= 10^5cost.length == 31 <= cost[i] <= 10^9
More Infosys Online Assessment questions
- Lowest Common Ancestor with a Changing RootOA · Seen Nov 2026
- Minimum Leaf Path Sum over All RootsOA · Seen Nov 2026
- Split Array to Minimize the Largest SumOA · Seen Nov 2026
- Cherry PickupOA · Seen Nov 2026
- Lexicographically Smallest Grid Path with One Letter ChangeOA · Seen Nov 2026
- Minimum Cost to Supply Water with Wells and PipesOA · Seen Nov 2026
- Minimum Rounds to Complete All TasksOA · Seen Nov 2026
- Count Equal-Distinct Character PartitionsOA · Seen Oct 2026
- Maximum Alternating-Index Packet ValueOA · Seen Oct 2026
- Usable Water with Contaminated PillarsOA · Seen Oct 2026
Similar questions at other companies
- 0/1 KnapsackConfluent · OAConfluent interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Subarray SumStraive · OA
- Longest Increasing Price SubsequenceOpenAI · OAOpenAI interview questions
- Lowest-Cost Shirt Color ScheduleElevenLabs · OAElevenLabs interview questions
- Maximum Game Board ScoreJP Morgan Chase · OAJP Morgan Chase interview questions
- API Bandwidth AllocationArista Networks · OAArista Networks interview questions
- Maximum Points by Deleting ElementsIBM · OAIBM interview questions
- House RobberWalmart · OAWalmart interview questions
- Three-Resource 0/1 KnapsackMorgan Stanley · OAMorgan Stanley interview questions