Optimize Travel Costs and Generate Rotational Symmetric Numbers
Overview
This question evaluates algorithmic optimization and complexity-analysis skills by combining array-based time-dependent pricing for round-trip cost minimization with combinatorial generation of rotationally symmetric (strobogrammatic) k-digit numbers.
Scenario
You are building a travel-search engine that must
- show customers the cheapest round-trip they can book if departure and return prices vary by day, and
- generate all k-digit numbers that still look the same after a 180° rotation for fraud-detection image checks.
Question
Given two arrays, dep[i] = outbound ticket price on day i and ret[j] = return ticket price on day j, design an algorithm that returns the minimum possible total cost for any valid round-trip (depart before return). Analyze time and space complexity and discuss possible optimizations or alternative solutions. Given an integer k, generate all k-digit numbers that remain identical when rotated 180°. Provide an algorithm, analyze its complexity, and explain how your code handles corner cases.
Hints
Cheapest flight: pre-compute suffix minima or use two-pointer scan. Strobogrammatic: recurse from outer to inner, pairing digits {0,0},{1,1},{6,9},{8,8},{9,6}.