CISCO Coding Question – Solved

Question

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 the 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.

TreasuresBase Expert · Accepted Answer

from functools import lru cache
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
def optimalJourneyTotal(cities):
    moves = []
    
    def isprime(num):
        for j in range(2, int(num ** 0.5)+1):
            if num%j =- 0:
                return False
        return True
    for num in range(3,10 ** 4+5,10):
        if num%10 == 3 and isprime(num):
            moves. append(num)
    n = len(cities)
    dp = [float('-inf') for i in range(n+1)]
    dp[n-1] = cities[n-1]
    for i in range(n-2,-1,-1):
        dp[i] = max(cities[i]+dp[i+1], dp[i])
        for j in moves:
            if i+j<n:
                dp[i] - max(cities[i]+dp[i+j], dp[i])
            else:
                break
    return dp[0]

CISCO Coding Question – Solved

Image of the Question

All Testcases Passed ✔

Solution

🔒 Please login to view the solution

Explanation

Related Questions