Microsoft Coding OA | SDE 1 | May 3 2023

Question

Question1: Given an array A consisting of N integers, returns the maximum sum of two numbers whose digits add up to an equal sum.
if there are not two numbers whose digits have an equal sum, the function should return -1.
Constraints: N is integer within the range [1, 200000]
each element of array A is an integer within the range [1, 1000000000]

 

Example1:
Input:
A = [51, 71, 17, 42]
Output: 93
Explanation: There are two pairs of numbers whose digits add up to an equal sum: (51, 42) and (17, 71), The first pair sums up to 93

 

Example2:
Input:
A = [42, 33, 60]
Output: 102
Explanation: The digits of all numbers in A add up the same sum, and choosing to add 42 and 60 gives the result 102

 

Example3:
Input:
A = [51, 32, 43]
Output: -1
Explanation: All numbers in A have digits that add up to different, unique sums

Source Link https://leetcode.com/discuss/interview-question/1957999/microsoft-oa-march-2022

Comments

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,i,ans=-1;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++) cin>>a[i];
    unordered_map<int,vector<int>> m;
    for(auto i:a) {
        int x=i,sum=0;
        while(x) {sum+=x%10; x/=10;}
        m[sum].push_back(i);
    }
    for(auto i:m) {
        int x=*max_element(m[i.first].begin(),m[i.first].end()),y=-1;
        for(auto j:m[i.first]) {
            if(j!=x) y=max(y,j);
        }
        if(y!=-1) ans=max(ans,x+y);
    }
    cout<<ans;
}

Answer 1

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

int getDigitSum(int n){
    int sum=0;
    while(n>0){
        sum += n%10;
        n /= 10;
    }
    
    return sum;
}

int main()
{
    int n;
    cin>>n;
    int arr[n];
    
    unordered_map<int,priority_queue<int> >m;
    
    for(int i=0; i<n; i++) cin>>arr[i];
    
    for(int i=0; i<n; i++){
        int ele = arr[i];
        int digitSum = getDigitSum(ele);
        m[digitSum].push(ele);
    }
    
    int ans=-1;
    
    for(auto &x:m){
        if(x.second.size()>1){
            priority_queue<int> pq = x.second;
            int x = pq.top(); pq.pop();
            int y = pq.top();
            ans = max(ans, x+y);
        }
    }
    
    cout<<ans;
    
    return 0;
}

Answer 2

Easy short solution

• Time Complexity : O(N)
• Space Complexity : O(N)

/*
 * @param n : number for which sum if digits to be evaluated
 * @approach : divide by 10 and add remainder to a variable  
*/

int getDigitSum(int n)
{
    int ans = 0;
    while (n)
    {
        ans += (n % 10);
        n /= 10;
    }
    return ans;
}

/*
 * @param arr : array of elements
 * @param n : no of elements
 * @variable dp : to store largest 2 values having same digit sum
 * @for loop : for each of the element update largest 2 values with current value for evaluated digit sum
 * @variable ans : to store maximum sum of elements having same digit sum
*/

int getMaxSum(vector<int> &arr, int n)
{
    unordered_map<int, pair<int, int>> dp;
    int ans = 0;
    for (auto x : arr)
    {
        int digitSum = getDigitSum(x);
        pair<int, int> curr = dp[digitSum];
        if (x >= curr.first)
        {
            curr.second = curr.first;
            curr.first = x;
        }
        else if (x >= curr.second)
        {
            curr.second = x;
        }
        dp[digitSum] = curr;
        ans = max(ans,curr.first+curr.second);
    }
    return ans;
}

Comments

Time complexity is wrong

Answer 3

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

int digitSum(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}
int maxSumEqualDigitSum(vector<int>& A) {
    unordered_map<int, int> digitSumMap;
    int maxSum = -1;
    for (int num : A) {
        int ds = digitSum(num);
        if (digitSumMap.count(ds)) {
            maxSum = max(maxSum, digitSumMap[ds] + num);
            digitSumMap[ds] = max(digitSumMap[ds], num);
        } else {
            digitSumMap[ds] = num;
        }
    }
    return maxSum;
}
int main() {
    int N;
    cin >> N;
    vector<int> A (N);
    for(int i = 0; i  < N; i++) cin >> A[i];
    int result = maxSumEqualDigitSum(A);
    cout  << result << endl;
    return 0;
}

Answer 4

#include <bits/stdc++.h>
using namespace std;
#define int long long
int sumOfDigits(int x){
    int sum=0;
    while(x>0){
       sum+=x%10;
       x/=10;
    }
    return sum;
}
int32_t main() {
    int n;
    cin>>n;
    vector<pair<int,int>>vec(n);
    for(int i=0;i<n;i++)
    {
        cin>>vec[i].second;
        vec[i].first=sumOfDigits(vec[i].second);
    }
    sort(vec.begin(),vec.end());
    int i=0;int maxSum=-1;
    int curr_elem=vec[0].first;
    while(i<n){
      int j=i;
      while(j<n && vec[j].first==vec[i].first)
         j++;
      if(j-2>=0 && vec[j-1].first==vec[j-2].first)
      maxSum=max(maxSum,vec[j-1].second+vec[j-2].second);
      i=j;
    }
    cout<<maxSum<<endl;
    return 0;
}