Practice Projects

Find Missing and Repeated Values

Problem Statement

Aapko ek 0-indexed 2D integer matrix grid di gayi hai, jiska size n * n hai aur usme values [1, n²] range mein hain.

Har integer ek baar appear hota hai except ek number ‘a’ jo do baar appear hota hai aur ek number ‘b’ jo missing hai.

Aapka task yeh hai ki aap repeat hone wala number ‘a’ aur missing number ‘b’ ko find karein.

Aapko ek 0-indexed integer array ans return karna hai jiska size 2 ho, jisme ans[0] equals to ‘a’ aur ans[1] equals to ‘b’ ho.

Example 1:

Input: grid = [[1,3],[2,2]] Output: [2,4] Explanation: Number 2 repeat ho raha hai aur number 4 missing hai, toh answer hai [2,4].

Example 2:

Input: grid = [[9,1,7],[8,9,2],[3,4,6]] Output: [9,5] Explanation: Number 9 repeat ho raha hai aur number 5 missing hai, toh answer hai [9,5].

Constraints:

  • 2 <= n == == grid[i].length <= 50

  • 1 <= grid[i][j] <= n * n

 

 
Practice Projects

Find Missing and Repeated Values

Count Occurrences:
~ Pehle ek 1D array (isko count kehte hain) banao jiska size 𝑛 2
ho aur sab elements ko 0 se initialize karo.

Grid ko traverse karo aur har element ke liye, corresponding index mein count array mein increment karo.

Identify Repeated and Missing Numbers:Grid traverse karne ke baad, count array ko dekho.
Jis index par count 2 hai, woh repeated number 𝑎 hai.

Jis index par count 0 hai, woh missing number 𝑏 hai.Return the Result:In dono values ko ek array ans mein store karo jahan ans[0] = a (repeated number) aur ans[1] = b (missing number) ho.ans array ko return karo.

Approach

Time Complexity:

  1. Counting Occurrences:

    • Hamne grid ko traverse kiya aur har element ka count increase kiya. Yeh operation O(n²) time leta hai, kyunki grid ka size n * n hai.

  2. Identifying Repeating and Missing Numbers:

    • Hamne count array ko traverse kiya jo n2n^2 size ka hai. Yeh operation bhi O(n²) time leta hai.

So, overall time complexity O(n²) hoti hai, kyunki yeh dominate karta hai baaki operations ko.

Space Complexity:

  1. Count Array:

    • Hamne ek 1D array count banaya jiska size n2+1n^2 + 1 hai. Isliye space complexity O(n²) hoti hai.

Is approach mein extra space sirf count array ke liye lagta hai, jo n2n^2 size ka hai. Isliye overall space complexity O(n²) hoti hai.

Solution

				
					function findRepeatingAndMissingNumbers(grid) {
    const n = grid.length;  // size of the grid
    const max_value = n * n;
    
    // Initialize the count array
    const count = new Array(max_value + 1).fill(0);
    
    // Count occurrences of each number in the grid
    for (let row of grid) {
        for (let num of row) {
            count[num]++;
        }
    }
    
    // Identify the repeating and missing numbers
    let repeating = -1, missing = -1;
    for (let num = 1; num <= max_value; num++) {
        if (count[num] === 2) {
            repeating = num;
        } else if (count[num] === 0) {
            missing = num;
        }
    }
    
    return [repeating, missing];
}

// Example usage
const grid1 = [[1, 3], [2, 2]];
console.log(findRepeatingAndMissingNumbers(grid1));  // Output: [2, 4]

const grid2 = [[9, 1, 7], [8, 9, 2], [3, 4, 6]];
console.log(findRepeatingAndMissingNumbers(grid2));  // Output: [9, 5]

Grid Initialization:

You start with a grid (2D array) that contains numbers ranging from 1 to n2n^2, but one number repeats and one number is missing.

Counting Occurrences:

First, you create an array called count to keep track of how many times each number appears in the grid. This array is initialized with zeros and its size is n2+1n^2 + 1 to cover all possible numbers from 1 to n2n^2.

Traversing the Grid:

Then, you go through each element in the grid. For each number found in the grid, you increase its corresponding value in the count array by 1.

Identifying the Repeated and Missing Numbers:

After counting the occurrences, you scan the count array to find the repeated and missing numbers.

The repeated number is the one whose count is 2.

The missing number is the one whose count is 0.

Returning the Result:

Finally, you put the repeated and missing numbers into an array and return that array.

Solution

				
					#include <iostream>
#include <vector>
using namespace std;

vector<int> findRepeatingAndMissingNumbers(vector<vector<int>>& grid) {
    int n = grid.size();  // size of the grid
    int max_value = n * n;
    
    // Initialize the count array
    vector<int> count(max_value + 1, 0);
    
    // Count occurrences of each number in the grid
    for (const auto& row : grid) {
        for (int num : row) {
            count[num]++;
        }
    }
    
    // Identify the repeating and missing numbers
    int repeating = -1, missing = -1;
    for (int num = 1; num <= max_value; num++) {
        if (count[num] == 2) {
            repeating = num;
        } else if (count[num] == 0) {
            missing = num;
        }
    }
    
    return {repeating, missing};
}

int main() {
    vector<vector<int>> grid1 = {{1, 3}, {2, 2}};
    vector<int> result1 = findRepeatingAndMissingNumbers(grid1);
    cout << "Repeated: " << result1[0] << ", Missing: " << result1[1] << endl;  // Output: 2, 4

    vector<vector<int>> grid2 = {{9, 1, 7}, {8, 9, 2}, {3, 4, 6}};
    vector<int> result2 = findRepeatingAndMissingNumbers(grid2);
    cout << "Repeated: " << result2[0] << ", Missing: " << result2[1] << endl;  // Output: 9, 5