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
Hint
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 A1, A2, …, AN 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 ≤ 106
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:
using namespace std;
void repeated_Numbers(vector<int> A) {
long long int sct_a = 0;
long long int sct_sum_sq = 0;
long long int srxp_b;
long long int srxp_sum_sqq;
long long int i = 0;
for(i = 0; i < A.size(); i++){
sct_a = sct_a + (long long int)A[i];
sct_sum_sq = sct_sum_sq + (long long int)A[i]*A[i];
}
srxp_b = (long long int)(A.size())*(A.size()+1)/2;
srxp_sum_sqq = (long long int)(A.size())*(A.size()+1)*(2*A.size()+1)/6;
long long int diff_sum_sq = srxp_sum_sqq - sct_sum_sq;
long long int diff_a = srxp_b - sct_a;
long long int toggle = diff_sum_sq/diff_a;
long long int miss = (toggle + diff_a)/2;
long long int repp = miss - diff_a;
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;
}
