Largest K such that both K and -K exist in array

Microsoft Online Assessment, Largest K such that both K and -K exist in array

Largest K such that both K and -K exist in array

Given an array A of N integers, returns the largest integer K > 0 such that both values K and -K exist in array A. If there is no such integer, the function should return 0.

Also See: Microsoft Online Assessment Questions and Solution

Example 1:

Input: [3, 2, -2, 5, -3]
Output: 3

Example 2:

Input: [1, 2, 3, -4]
Output: 0

Solution:

This task is very easy. It is a bit more difficult than finding of a maximum value in given array. The only thing we have to add is check if this array contains the same value on the opposite side of zero. In other words we have to check all positive values in the array and check if there are values with the same absolute value but negative sign. There is the only data structure which has constant complexity for access to unsorted items, this is a hash table.

So at first we add all given values to a hash table.

Then pass through all items of the table and check if positive item has the same absolute value but with negative sigh.

Each time if we meet an absolute value bigger than already found maximum value keep it as a new maximum value.

Program C++:

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int solution(const vector<int>& input){
    unordered_set<int> s(input.begin(),input.end());
    int max_value = 0;
    for(auto n : s){
        if((abs(n) > max_value) && (s.count(-n) != 0) ) {
            max_value = n;
        }
    }
    return max_value;
}

int main() {

    cout << solution({3, 2, -2, 5, -3}) << " Expected: 3" << endl;

    cout << solution({1, 2, 3, -4}) << " Expected: 0" << endl;

    return 0;
}

Program Python:

def solution(arr):
    
    arr = sorted(arr)
    i,j = 0, len(arr)-1
    while i < j:
        if arr[i]+arr[j] == 0:
            return arr[j]
        elif abs(arr[i]) > arr[j]:
            i += 1
        elif abs(arr[i]) < arr[j]:
            j-=1     
    return 0
    
print(solution([3, 2, -2, 5, -3]))

Program Java:

 public static void main(String[] s){
        int[] arr = {-41,3,2,5,41};
        System.out.println(largestNumWithNegPair(arr));
 }
 private static int largestNumWithNegPair(int[] arr){
        HashSet<Integer> set = new HashSet<>();
        int curMax = 0;
        for (int a:arr) {
            // if the negated counter part is already existing, consider the number for largestNum selection.
            if(set.contains(a*-1))
                curMax = Math.max(curMax,Math.abs(a));
            else
                //keep track of the numbers read so far.
                set.add(a);
        }
 return curMax;
 }

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA Online Assessment 2021 Questions and Answers

Microsoft Online Assessment 2021 Questions

Leave a Comment