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:

from typing import List
def largest_k(nums: List[int]) -> int:
    result = 0
    for i in nums:
        if i < 0 and -i in nums:
            result = max(result, -i)
    return result
if __name__ == '__main__':
    nums = [int(x) for x in input().split()]
    res = largest_k(nums)
    print(res)

Program Javascript:

function largestK(nums) {
    let maxValue = 0;
    const size = nums.length;
    for (let i = 0; i <= size; i++) {
        if (Math.abs(nums[i]) > maxValue && nums.indexOf(-nums[i]) !== -1) {
            maxValue = nums[i];
        }
    }
    return maxValue;
}
function splitWords(s) {
    return s == "" ? [] : s.split(' ');
}
function* main() {
    const nums = splitWords(yield).map((v) => parseInt(v));
    const res = largestK(nums);
    console.log(res);
}
class EOFError extends Error {}
{
    const gen = main();
    const next = (line) => gen.next(line).done && process.exit();
    let buf = '';
    next();
    process.stdin.setEncoding('utf8');
    process.stdin.on('data', (data) => {
        const lines = (buf + data).split('\n');
        buf = lines.pop();
        lines.forEach(next);
    });
    process.stdin.on('end', () => {
        buf && next(buf);
        gen.throw(new EOFError());
    });
}

Program Java:

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
class Solution {
    public static int largestK(List<Integer> nums) {
        HashSet<Integer> set = new HashSet<>();
        int curMax = 0;
        for (int a : nums) {
            if (set.contains(-a))
                curMax = Math.max(curMax, Math.abs(a));
            else
                set.add(a);
        }
        return curMax;
    }
    public static List<String> splitWords(String s) {
        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> nums = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
        scanner.close();
        int res = largestK(nums);
        System.out.println(res);
    }
}

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions

Leave a Comment