How should I practice Lock Code?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs online assessment problems in FastPrep.

Is Lock Code associated with Goldman Sachs?

FastPrep tags this as a Goldman Sachs online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Math

Lock Code

Learn this problem

● Hard

Goldman SachsOA

Problem statement

You are given an array of integers codeSequence of length n and an integer maxValue. A locking system allows you to modify any number in the array to any integer less than or equal to maxValue at a cost of 1 per change.

Two numbers are co-prime if their greatest common divisor (GCD) is 1. To unlock the repository, you need to select a number from the array that is co-prime with all other numbers in the array.

The lock's code is calculated as the maximum possible value of: selected number - total modification cost

Your task is to determine the lock code by selecting an optimal number from the array after modifications that is co-prime with all other numbers in the array.

Function

decryptCodeLock(codeSequence: int[], maxValue: int) → int

Complete the function decryptCodeLock in the editor with the following parameters:

int codeSequence[n]: the array presented by the code lock
int maxValue: the maximum possible value for any element in the array

Returns

int: the lock code

FastPrep's sincere 🌸thanks🌸 go to our exceptional friend for their meaningful, valued contribution!

Examples

Example 1

codeSequence = [3, 2, 4]maxValue = 6return = 4

Optimally:

Change the element at the third position to 5 at the cost of 1 unit: codeSequence' = [3, 2, 5].

Choose the element 5 since it is co-prime with both 2 and 3.

Calculate lock code = selected number - cost = 5 - 1 = 4.

Return 4 as the answer.

Example 2

codeSequence = [1, 2, 3]maxValue = 6return = 4

Optimally, change the second and third elements to 5 and 6 at a cost of 2 units, resulting in [1, 5, 6]. The number 6 is coprime with both 1 and 5. The lock's code is 6 - 2 (cost) = 4.

Example 3

codeSequence = [2, 4, 6, 8]maxValue = 8return = 6

Optimally, change the third element to 7 at a cost of 1 unit, resulting in [2, 4, 7, 8]. The number 7 is coprime with 2, 4, and 8. The lock's code is 7 - 1 (cost) = 6.

Constraints

1 ≤ n ≤ 10^3
1 ≤ maxValue ≤ 10^9
1 ≤ codeSequence[i] ≤ maxValue