Largest K such that both K and -K exist in array Microsoft OA 2023

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

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.

Example 1:

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

Example 2:

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

Also See: Amazon OA Online Assessment 2023 Questions and Answers

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: Largest K such that both K and -K exist in array Solution in 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: Largest K such that both K and -K exist in array Solution in 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: Largest K such that both K and -K exist in array Solution in 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;
 }

Microsoft Online Assessment 2023 Questions List

Leave a Comment

one × 4 =