Given an unsorted array of size N of positive integers. One number 'A' from set {1, 2, …N} is missing and one number 'B' occurs twice in array. Find these two numbers. Note: If you find multiple answers then print the Smallest number found. Also, expected solution is O(n) time and constant extra space. - Codeprg

Breaking

programing News Travel Computer Engineering Science Blogging Earning

Thursday, 18 June 2020

Given an unsorted array of size N of positive integers. One number 'A' from set {1, 2, …N} is missing and one number 'B' occurs twice in array. Find these two numbers. Note: If you find multiple answers then print the Smallest number found. Also, expected solution is O(n) time and constant extra space.

Given an unsorted array of size N of positive integers. One number 'A' from set {1, 2, …N} is missing and one number 'B' occurs twice in array. Find these two numbers.

Note: If you find multiple answers then print the Smallest number found. Also, the expected solution is O(n) time and constant extra space.


Business, Paper, Coffee, Table, Cup, Desktop, Tea

#include <bits/stdc++.h>

using namespace std;

int main() {
    //code
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int x, b[n + 1];
        memset(b, 0, sizeof(b));
        int mis, rep, f = 0;
        for (int i = 0; i < n; ++i) {
            cin >> x;
            b[x]++;
        }

        for (int i = 1; i < n + 1; ++i) {
            if (b[i] == 0)
                mis = i;
            if (b[i] == 2)
                rep = i;

        }

        cout << rep << " " << mis << endl;
    }
    return 0;
}