Company: CISCO

A Profitable Journey

A traveler moves through cities represented by an array of integers, where each integer indicates the money spent (negative) or earned (positive) in that city per day. The journey starts at city 0 and ends at city (n-1). The traveler can move to either an adjacent city or a city that is p steps away, where p is any prime number ending in 3.

Determine the maximum money th e traveler can have at the end of the journey.

Example:
cities = [0, 100, 200, -500, -100, -150, -50]
The optimal journey results in a total amount of 100.
The traveler starts from the 0th city, moves to the 1st and earns 100, moves to the 2nd city to get 100 + 200 = 300, then to the 5th city (2 + 3 = 5) to get 300 + (-150) = 150, then to the 6th city to get 150 + (-50) = 100.
The traveler only moves to (i + 1)th or (i + 3)th cities since 3 is the only prime that ends with the digit 3 in the range of the array.

Function Description:
Complete the function optimalJourneyTotal in the editor with the following parameters:
int cities[n]: Each cities[i] represents the amount of money earned or spent in the i-th city.

Returns:
int: The maximum amount of money the traveler can have at the end of the journey.

Sample Input:
cities = [-10, -20, 80, -40, -10]
Sample Output:
10
Explanation:
Starting from 0, the traveler moves through all cities in sequence to earn: 0 - 20 + 80 - 40 - 10 = 10.

Sample Case 1:
Input: cities = [-2, -10, -10, -3]
Output: -5
Explanation:
From index 0, the traveler moves to index 3 (0 + 3) to obtain a total of -2, then to index 4 to obtain a total of -2 + (-3) = -5. Show More

Given an n x m grid, where rows are numbered from 7 to n and columns from 1 to m, there are x blocked cells. Their positions are specified by the array blockedPositions[i][] where blockedPositions[i][1] represents the row and blockedPositions[i][2] represents the column position, using 1-based indexing.

Starting from the top-left cell (1, 1), the goal is to reach the bottom-right cell (n, m) wi thout visiting any blocked cells. Movement is allowed only up, down, left, or right.

The strength of a path is defined as the minimum Manhattan distance from each cell in the path to the nearest blocked cell. To calculate the strength of a specific path, an array minDist[] is created, where minDist[i] represents the minimum distance to any blocked cell for the ith cell visited. The strength of the path is given by min(minDist[]).

Among all possible paths from (1, 1) to (n, m), determine the path that maximizes strength. If multiple paths have the same maximum strength, select the one that visits the fewest cells.

Return two integers: the maximum strength achievable and the minimum number of cells visited. If it is impossible to navigate from (1, 1) to (n, m), return [-1, -1].

Note: The Manhattan distance between cells (a, b) and (c, d) is defined as abs(a-c) + abs(b-d).

Example n=4 Show More