ENCJMAY3-Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Anuska Sinha
Tester: Sandeep Singh
Editorialist: Anuska Sinha

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Math

PROBLEM:

You are given a read-only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Print A and B.

EXPLANATION:

Just remove the doubles from the array and print the missing number between 1 to n. After taking input we can take the sum of the set of the array. We need set since set removes the duplicate. We can subtract this sum from the sum of the original array to find the duplicate number. We can then subtract the sum of the set of the array A from the sum of all the numbers from 1 to n to find the missing number.

SOLUTIONS:

Setter's Solution 
T=int(input())
while(T!=0):
    T=T-1
    N=int(input())
    A= list(map(int, input( ).split())) 
    x=sum(A)-sum(set(A))
    k=int(N*(N+1)/2)-sum(set(A))
    print(x)
    print(k)
Tester's Solution 
void solve(){
    
    int n, i;
 
    unordered_map<int, bool> mp;
    cin >> n;
 
    int arr[n];
 
    for(i = 0; i < n; ++i)
        cin >> arr[i];
    
    int a, b, sum = 0;
 
    for(i = 0; i < n; ++i){
        if(mp[arr[i]])
            a = arr[i];
        mp[arr[i]] = 1;
        sum += arr[i];
    }
 
    sum -= a;
 
    b = (n * (n + 1))/2 - sum;
 
    cout <<a<<" "<<b<<endl;
}
int main(){
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif
    int t;
    cin>>t;
    while(t--)
        solve();
}
2 Likes