Missing Coin Sum | Sorting and Searching | CSES Problem Set скачать в хорошем качестве

Missing Coin Sum | Sorting and Searching | CSES Problem Set

Let ans be the smallest sum that cannot be formed using the first i minus 1 coins. This means we can already form all sums from 1 to ans minus 1. Now consider the i-th coin with value x. Since the array is sorted, we always process the smallest coins first. Case 1 If x is greater than ans Right now, we can form all sums from 1 to ans minus 1. If we include the new coin x, the smallest sum we can form using it is x itself. But if x is strictly greater than ans, then there is no way to form the sum ans. So we have found a gap. Therefore, the answer is ans. Case 2 If x is less than or equal to ans We can already form all sums from 1 to ans minus 1. By adding coin x to all those sums, we can now form new sums from 1 plus x up to ans minus 1 plus x. Also, the value x itself can be formed. Since x is less than or equal to ans, this new range overlaps or directly touches the previous range. So the combined achievable range becomes from 1 up to ans minus 1 plus x. Now the new smallest unachievable sum becomes ans plus x. Core idea As long as the current coin is less than or equal to ans, we can safely extend our reachable range. The moment we find a coin greater than ans, that ans is our final answer. HINGLISH Let ans be the smallest sum jo hum first i minus 1 coins se nahi bana pa rahe hain. Iska matlab yeh hai ki hum 1 se lekar ans minus 1 tak ke saare sums bana sakte hain. Ab consider karo i-th coin jiska value x hai. Array sorted hai, isliye hum smallest coins se start kar rahe hain. Case 1 Agar x ans se bada hai Abhi tak hum 1 se ans minus 1 tak ke saare sums bana sakte hain. Agar hum naya coin x use karein, toh sabse chhota sum jo is coin se banega woh x hi hoga. Lekin agar x ans se bada hai, toh beech ka sum ans kabhi ban hi nahi sakta. Yahan ek gap mil gaya. Isliye answer wahi ans hoga. Case 2 Agar x ans se chhota ya barabar hai Hum already 1 se ans minus 1 tak ke saare sums bana sakte hain. Ab agar hum coin x ko in sab sums ke saath add karein, toh naye sums milenge 1 plus x se lekar ans minus 1 plus x tak. Aur x khud bhi ban sakta hai. Kyunki x ans se chhota ya barabar hai, toh naya range purane range ko touch ya overlap karega. Ab combined range ban jaayega 1 se lekar ans minus 1 plus x tak. Isliye ab jo naya smallest unachievable sum hoga woh ans plus x ho jaayega. Core intuition Jab tak current coin ans se chhota ya equal hai, tab tak koi gap create nahi hota. Jaise hi coin ans se bada milta hai, wahi hamara answer hota hai.