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

• Maximal Network Rank Solution
• Min Deletions To Obtain String in Right Format
• Day of week that is K days later Solution
• Minimum Adjacent Swaps to Make Palindrome Solution
• Lexicographically Smallest String
• Longest Substring Without Two Contiguous Occurrences of Letter
• String Without 3 Identical Consecutive Letters
• Microsoft OA Longest Semi-Alternating Substring
• Microsoft OA Min Steps to Make Piles Equal Height
• Max Inserts to Obtain String Without 3 Consecutive ‘a’
• Concatenated String Length with unique Characters
• Largest K such that both K and -K exist in array
• Microsoft OA Min Adj Swaps to Group Red Balls
• Maximum Length of a Concatenated String with Unique Characters
• Microsoft OA Unique Integers That Sum Up To 0
• Find N Unique Integers Sum up to Zero
• Microsoft OA Particle Velocity Solution
• Microsoft OA Arithmetic Slices Solution
• Microsoft OA Widest Path Without Trees Solution
• Microsoft OA Jump Game Solution
• Microsoft OA Fair Indexes Solution