If you\u2019re preparing\u00a0for coding interviews, the “Missing And\u00a0Repeating” problem\u00a0is a classic! In this blog, we\u2019ll explain\u00a0the problem, walk\u00a0you through brute\u00a0force, better, and optimal\u00a0solutions, and\u00a0make everything\u00a0easy to understand\u00a0with code comments, dry runs, and\u00a0clear explanations.<\/p>\n\n\n\n
Given an unsorted array arr<\/em><\/strong> of positive integers. One number a<\/strong> from the set [1, 2,….,n]<\/strong> is missing and one number b<\/strong> occurs twice in the array. Find numbers a<\/strong> and b<\/strong>.<\/p>\n\n\n\n Note:<\/strong> The test cases are generated such that there always exists one missing and one repeating number within the range [1,n]<\/strong>.<\/p>\n\n\n\n Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Examples:<\/strong><\/p>\n\n\n\n Constraints:<\/strong> Let\u2019s solve the problem in the simplest way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large arrays.<\/p>\n\n\n\nInput: <\/strong>arr[] = [2, 2]
Output:<\/strong> [2, 1]
Explanation:<\/strong> Repeating number is 2 and smallest positive missing number is 1.<\/pre>\n\n\n\nInput: <\/strong>arr[] = [1, 3, 3] \nOutput:<\/strong> [3, 2]\nExplanation:<\/strong> Repeating number is 3 and smallest positive missing number is 2.<\/pre>\n\n\n\n
Input: <\/strong>arr[] = [4, 3, 6, 2, 1, 1]
Output:<\/strong> [1, 5]
Explanation:<\/strong> Repeating number is 1 and the missing number is 5.<\/pre>\n\n\n\n
2 \u2264 arr.size() \u2264 106<\/sup>
1 \u2264 arr[i] \u2264 arr.size()<\/p>\n\n\n
\n\n\n\nBrute Force Solution (Nested Loops)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
For each number from 1 to n, count how many times it appears in the array.<\/li>\n\n\n\n\n
We check every number, so we\u2019re sure to find both the missing and repeating numbers.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n