[Solved] Get the Shadow Contest Problem

Get the Shadow: Given an unsorted array A[] of size N of positive integers. One number ‘a’ from set {1, 2, N} is missing and one number ‘b’ occurs twice in array. The task is to find the repeating and the missing.

Get the Shadow Contest

Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A₁, A₂, …, A_N denoting the elements of the array.

Output:
For each testcase, in a new line, print b, which is the repeating number, followed by a, which is the missing number, in a single line.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10⁶
1 ≤ A[i] ≤ N

Example:
Input:
2
2
2 2
3 
1 3 3

Output:
2 1
3 2

Explanation:
Testcase 1: Repeating number is 2 and smallest positive missing number is 1.
Testcase 2: Repeating number is 3 and smallest positive missing number is 2.

Solution:

#include <bits/stdc++.h>
using namespace std;

void repeated_Numbers(vector<int> A) {
    long long int acta = 0;
    long long int actsumsq = 0;
    long long int expb;
    long long int expsumsq;
    long long int i = 0;
    
    for(i = 0; i < A.size(); i++){
        acta = acta + (long long int)A[i];
        actsumsq = actsumsq + (long long int)A[i]*A[i];
    }
    
    expb = (long long int)(A.size())*(A.size()+1)/2;
    expsumsq = (long long int)(A.size())*(A.size()+1)*(2*A.size()+1)/6;
    
    long long int diffsumsq = expsumsq - actsumsq;
    long long int diffa = expb - acta;
    
    long long int toggle = diffsumsq/diffa;
    
    long long int miss = (toggle + diffa)/2;
    long long int repp = miss - diffa;
    
    cout<<(int)repp<<" "<<(int)miss<<endl;

    return ;
}

int main() {
	int T;
	cin>>T;
	while(T--){
	    int N;
	    cin>>N;
	    vector<int> vect;
	    
	    for(int i=0; i<N; i++){
	        int temp;
	        cin>>temp;
	        vect.push_back(temp);
	    }
	    repeated_Numbers(vect);
	}
	return 0;
}

Happy Learning – If you require any further information, feel free to contact me.