You need to build a road in a rugged terrain You know the sea level of

Rugged Terrain Road Construction

You need to build a road in a rugged terrain. You know the sea level of each segment of the rugged terrain, i.e., the i-th segment is L_i meters from sea level.

Infosys HackWithlnfy 2025

You need to transform the terrain into a strictly downward sloping terrain for the road, i.e., for each i-th segment where 2 ≤ i ≤ N, the resultant L_i-1 > L_i. To achieve this, you employ a powerful digging team to help reduce the sea level of the segments. On day D, the team can reduce the sea level of each scheduled segment by 2^D-1 meters.

You are allowed to assign the team to dig on multiple segments and/or dig on the same segments for multiple days.

Your task is to find the minimum number of days needed to transform the terrain as per the given requirements.

Parameters:

N :: INTEGER

The first line contains an integer, N, denoting the number of elements in L.

Range: 1 ≤ N ≤ 10⁵

L :: INTEGER ARRAY

Each of the N subsequent lines (where 1 ≤ i ≤ N) contains an integer describing L_i, the sea level of the i-th segment.

Range: -10⁹ ≤ L[i] ≤ 10⁹

Example Cases

Case# 1

Input:

2
3
3

Output:

1

We can dig on the 2nd segment, reducing it from 3-meter sea level to 2, resulting in {3, 2}, which is strictly decreasing.

Case# 2

Input:

2
5
-3

Output:

0

It is already strictly decreasing before the start.

Case# 3

Input:

4
-1
1
1
1

Output:

3

One possible way:

• On day 1, we can dig on the 1st and 4th segments, resulting in {-2, 1, 1, 0}.
• On day 2, we can dig on the 3rd and 4th segments, resulting in {-2, 1, -1, -2}.
• On day 3, we can dig on the 2nd, 3rd, and 4th segments, resulting in {-2, -3, -5, -6}.

Infosys HackWithlnfy 2025

Road Construction Java Program

import java.util.*;

public class RoadConstruction {
    public static int minimumDays(int N, int[] L) {
        if (N == 1 || isStrictlyDecreasing(L)) {
            return 0;
        }
        int days = 0;
        boolean needsMore = true;
        while (needsMore) {
            days++;
            int reduction = (1 << (days - 1));
            needsMore = false;
            int[] temp = Arrays.copyOf(L, N);
            for (int i = N - 2; i >= 0; i--) {
                if (temp[i] <= temp[i + 1]) {
                    int target = temp[i + 1] + 1;
                    temp[i] -= reduction;
                    if (i > 0 && temp[i - 1] <= temp[i]) {
                        needsMore = true;
                    }
                }
            }
            L = Arrays.copyOf(temp, N);
            if (!needsMore && isStrictlyDecreasing(L)) {
                return days;
            }
        }
        return days;
    }
    
    private static boolean isStrictlyDecreasing(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] <= arr[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        test(new int[]{3, 3}, 1);
        test(new int[]{5, -3}, 0);
        test(new int[]{-1, 1, 1, 1}, 3);
    }
    
    private static void test(int[] L, int expectedResult) {
        int result = minimumDays(L.length, L);
        System.out.println("Input: " + Arrays.toString(L));
        System.out.println("Expected: " + expectedResult);
        System.out.println("Got: " + result);
        System.out.println("Test " + (result == expectedResult ? "PASSED" : "FAILED"));
        System.out.println();
    }
}
    

Key Features:

• Main Algorithm (minimumDays):
  • Checks if the terrain is already strictly decreasing.
  • Iteratively reduces heights from right to left.
  • Uses binary reduction (2^(d-1)) for each day.
  • Continues until terrain is strictly decreasing.
• Helper Method (isStrictlyDecreasing):
  • Verifies if the terrain is strictly decreasing.
• Test Functionality:
  • Includes three test cases.
  • Prints detailed test results.

Python Code: Minimum Days Calculation

    def minimum_days(N: int, L: list) -> int:
        def is_strictly_decreasing(arr: list) -> bool:
            return all(arr[i-1] > arr[i] for i in range(1, len(arr)))
        
        if N == 1 or is_strictly_decreasing(L):
            return 0
        
        days = 0
        needs_more = True
        
        while needs_more:
            days += 1
            reduction = 1 << (days - 1)
            needs_more = False
            temp = L.copy()
            
            for i in range(N-2, -1, -1):
                if temp[i] <= temp[i + 1]:
                    target = temp[i + 1] + 1
                    required = abs(temp[i] - target)
                    temp[i] -= reduction
                    if i > 0 and temp[i - 1] <= temp[i]:
                        needs_more = True
            
            L = temp.copy()
            if not needs_more and is_strictly_decreasing(L):
                return days
        
        return days
    
    def test_cases():
        test_inputs = [([3, 3], 1), ([5, -3], 0), ([-1, 1, 1, 1], 3)]
        for i, (arr, expected) in enumerate(test_inputs, 1):
            result = minimum_days(len(arr), arr.copy())
            print(f"Test Case #{i}")
            print(f"Input: {arr}")
            print(f"Expected: {expected}")
            print(f"Got: {result}")
            print(f"Status: {'PASSED' if result == expected else 'FAILED'}")
            print()
    
    if __name__ == "__main__":
        test_cases()
    

Pythonic Improvements

• More concise syntax:
• List comprehensions
• Built-in all() function for checking decreasing property
• Python's simpler array copying with list.copy()
• Type hints added for better code readability and IDE support

Main Algorithm Features

• Checks if terrain is already strictly decreasing
• Uses binary reduction (2^(d-1)) for each day
• Works from right to left to reduce heights
• Continues until the terrain becomes strictly decreasing

Test Functionality

• Includes the three original test cases
• Prints detailed test results
• Structured as a separate function

Usage

To use this code, you can either:

• Run it as is to see the test cases
• Uncomment the input section at the bottom to use it with custom input
• Import the minimum_days function to use in another program

Test Cases

    [3, 3] → 1 day
    [5, -3] → 0 days (already decreasing)
    [-1, 1, 1, 1] → 3 days
    

Infosys HackWithlnfy 2025

JavaScript

/**
 * Calculates minimum days needed to make terrain strictly decreasing
 * @param {number} N - Number of elements in terrain array
 * @param {number[]} L - Array of terrain heights
 * @returns {number} Minimum number of days needed
 */
function minimumDays(N, L) {
    // Helper function to check if array is strictly decreasing
    const isStrictlyDecreasing = (arr) => {
        return arr.every((val, i) => i === 0 || arr[i - 1] > val);
    };

    // Handle base cases
    if (N === 1 || isStrictlyDecreasing(L)) {
        return 0;
    }

    let days = 0;
    let needsMore = true;

    while (needsMore) {
        days++;
        const reduction = 1 << (days - 1); // Calculate 2^(d-1)

        // Try reducing heights starting from right to make it strictly decreasing
        needsMore = false;

        // Create a copy of array to track changes for this day
        const temp = [...L];

        // Start from second-to-last element and work backwards
        for (let i = N - 2; i >= 0; i--) {
            // If current element needs to be reduced to make it strictly decreasing
            if (temp[i] <= temp[i + 1]) {
                // Calculate how much we need to reduce to make it strictly decreasing
                const target = temp[i + 1] + 1;
                const required = Math.abs(temp[i] - target);

                // Apply reduction
                temp[i] -= reduction;

                // If we still need more days after this reduction
                if (i > 0 && temp[i - 1] <= temp[i]) {
                    needsMore = true;
                }
            }
        }

        // Update original array with changes
        L = [...temp];

        // Check if we have achieved strictly decreasing property
        if (!needsMore && isStrictlyDecreasing(L)) {
            return days;
        }
    }

    return days;
}

/**
 * Run test cases for the road construction problem
 */
function runTestCases() {
    const testCases = [
        { input: [3, 3], expected: 1, description: "Case #1: Equal heights" },
        { input: [5, -3], expected: 0, description: "Case #2: Already decreasing" },
        { input: [-1, 1, 1, 1], expected: 3, description: "Case #3: Multiple days needed" }
    ];

    testCases.forEach((testCase, index) => {
        const result = minimumDays(testCase.input.length, [...testCase.input]);
        console.log(`\n${testCase.description}`);
        console.log(`Input: [${testCase.input}]`);
        console.log(`Expected: ${testCase.expected}`);
        console.log(`Got: ${result}`);
        console.log(`Status: ${result === testCase.expected ? 'PASSED ✅' : 'FAILED ❌'}`);
    });
}

// Example usage with Node.js readline interface
const readFromConsole = async () => {
    const readline = require('readline').createInterface({
        input: process.stdin,
        output: process.stdout
    });

    const question = (query) => new Promise(resolve => readline.question(query, resolve));

    try {
        const N = parseInt(await question('Enter number of segments: '));
        const L = [];
        
        for (let i = 0; i < N; i++) {
            const height = parseInt(await question(`Enter height for segment ${i + 1}: `));
            L.push(height);
        }

        const result = minimumDays(N, L);
        console.log(`\nMinimum days needed: ${result}`);
    } catch (error) {
        console.error('Error:', error.message);
    } finally {
        readline.close();
    }
};

// Run test cases
console.log("Running test cases:");
runTestCases();

// Uncomment to run interactive console input
// readFromConsole();

This JavaScript implementation includes several improvements and features:

• Modern JavaScript features:
• Arrow functions
• Spread operator for array copying
• Template literals for string formatting
• Async/await for console input handling

Key components:

• Main minimumDays function with JSDoc documentation
• Helper function for checking strictly decreasing property
• Comprehensive test suite
• Interactive console input option

The algorithm maintains the same logic:

• Checks for base cases
• Uses binary reduction (2^(d-1))
• Works right to left to reduce heights
• Continues until terrain is strictly decreasing

To use this code, you can:

• Run it directly to see test cases
• Uncomment the readFromConsole() call for interactive input
• Import the minimumDays function to use in another program

Example usage in Node.js:

// Import the function
const result = minimumDays(4, [-1, 1, 1, 1]);
console.log(result); // Output: 3

The code handles all test cases:

• [3, 3] → 1 day
• [5, -3] → 0 days
• [-1, 1, 1, 1] → 3 days

Road Construction C++ Program

This C++ program calculates the minimum number of days needed to make an array strictly decreasing.

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

class RoadConstruction {
private:
    // Helper function to check if array is strictly decreasing
    static bool isStrictlyDecreasing(const std::vector<int>& arr) {
        for(size_t i = 1; i < arr.size(); ++i) {
            if(arr[i-1] <= arr[i]) return false;
        }
        return true;
    }

public:
    static int minimumDays(int N, std::vector<int>& L) {
        // Handle base cases
        if(N == 1 || isStrictlyDecreasing(L)) {
            return 0;
        }

        int days = 0;
        bool needsMore = true;

        while(needsMore) {
            days++;
            int reduction = 1 << (days - 1); // Calculate 2^(d-1)

            // Try reducing heights starting from right to make it strictly decreasing
            needsMore = false;

            // Create a copy of array to track changes for this day
            std::vector<int> temp = L;

            // Start from second-to-last element and work backwards
            for(int i = N-2; i >= 0; --i) {
                // If current element needs to be reduced to make it strictly decreasing
                if(temp[i] <= temp[i + 1]) {
                    // Calculate how much we need to reduce to make it strictly decreasing
                    int target = temp[i + 1] + 1;
                    int required = std::abs(temp[i] - target);

                    // Apply reduction
                    temp[i] -= reduction;

                    // If we still need more days after this reduction
                    if(i > 0 && temp[i-1] <= temp[i]) {
                        needsMore = true;
                    }
                }
            }

            // Update original array with changes
            L = temp;

            // Check if we have achieved strictly decreasing property
            if(!needsMore && isStrictlyDecreasing(L)) {
                return days;
            }
        }

        return days;
    }
};

void runTestCase(const std::vector<int>& input, int expected, const std::string& description) {
    std::vector<int> testInput = input; // Create a copy for testing
    int result = RoadConstruction::minimumDays(testInput.size(), testInput);
    
    std::cout << "\nTest Case: " << description << std::endl;
    std::cout << "Input: ";
    for(size_t i = 0; i < input.size(); ++i) {
        std::cout << input[i];
        if(i < input.size() - 1) std::cout << ", ";
    }
    std::cout << std::endl;
    std::cout << "Expected: " << expected << std::endl;
    std::cout << "Got: " << result << std::endl;
    std::cout << "Status: " << (result == expected ? "PASSED ✓" : "FAILED ✗") << std::endl;
}

void runAllTests() {
    std::cout << "Running test cases..." << std::endl;
    
    runTestCase({3, 3}, 1, "Case 1: Equal heights");
    runTestCase({5, -3}, 0, "Case 2: Already decreasing");
    runTestCase({-1, 1, 1, 1}, 3, "Case 3: Multiple days needed");
}

int main() {
    // Run predefined test cases
    runAllTests();

    // Interactive mode
    char runInteractive;
    std::cout << "\nWould you like to run in interactive mode? (y/n): ";
    std::cin >> runInteractive;

    if(runInteractive == 'y' || runInteractive == 'Y') {
        int N;
        std::cout << "Enter number of segments: ";
        std::cin >> N;

        std::vector<int> L(N);
        for(int i = 0; i < N; ++i) {
            std::cout << "Enter height for segment " << (i+1) << ": ";
            std::cin >> L[i];
        }

        int result = RoadConstruction::minimumDays(N, L);
        std::cout << "\nMinimum days needed: " << result << std::endl;
    }

    return 0;
}
    

Infosys HackWithlnfy 2025

Features of the Implementation

• Object-Oriented Design:
  • Encapsulated in a RoadConstruction class
  • Static methods for utility functions
  • Private helper methods
• Modern C++ Features:
  • Use of std::vector for dynamic arrays
  • Range-based loops where appropriate
  • Proper const correctness
  • Pass by reference for efficiency
• Key Components:
  • Main algorithm in minimumDays
  • Helper function for checking strictly decreasing property
  • Comprehensive test suite
  • Interactive console input option

Algorithm Explanation

• Base case checking
• Binary reduction calculation: 2^(d-1)
• Right-to-left height reduction
• Iterative improvement until strictly decreasing

How to Use the Code

To use this code:

1. Compile with a C++ compiler (C++11 or later)
2. Run the executable
3. Choose between test cases or interactive mode

Test Cases

The program handles the following test cases:

• {3, 3} → 1 day
• {5, -3} → 0 days
• {-1, 1, 1, 1} → 3 days

Compilation and Running

To compile and run the program, use the following commands:

g++ -std=c++11 road_construction.cpp -o road_construction
./road_construction
       

C Code Example: Minimum Days Calculation

This page contains the C code to calculate the minimum days needed for a strictly decreasing sequence.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// Helper function to check if array is strictly decreasing
bool isStrictlyDecreasing(const int* arr, int size) {
    for(int i = 1; i < size; i++) {
        if(arr[i-1] <= arr[i]) return false;
    }
    return true;
}

// Function to calculate minimum days needed
int minimumDays(int N, int* L) {
    // Handle base cases
    if(N == 1 || isStrictlyDecreasing(L, N)) {
        return 0;
    }

    int days = 0;
    bool needsMore = true;

    // Allocate memory for temporary array
    int* temp = (int*)malloc(N * sizeof(int));
    if(temp == NULL) {
        printf("Memory allocation failed!\\n");
        exit(1);
    }

    while(needsMore) {
        days++;
        int reduction = 1 << (days - 1); // Calculate 2^(d-1)

        // Try reducing heights starting from right to make it strictly decreasing
        needsMore = false;

        // Copy array for this iteration
        memcpy(temp, L, N * sizeof(int));

        // Start from second-to-last element and work backwards
        for(int i = N-2; i >= 0; i--) {
            // If current element needs to be reduced to make it strictly decreasing
            if(temp[i] <= temp[i + 1]) {
                // Calculate how much we need to reduce to make it strictly decreasing
                int target = temp[i + 1] + 1;
                int required = abs(temp[i] - target);

                // Apply reduction
                temp[i] -= reduction;

                // If we still need more days after this reduction
                if(i > 0 && temp[i-1] <= temp[i]) {
                    needsMore = true;
                }
            }
        }

        // Update original array with changes
        memcpy(L, temp, N * sizeof(int));

        // Check if we have achieved strictly decreasing property
        if(!needsMore && isStrictlyDecreasing(L, N)) {
            free(temp);
            return days;
        }
    }

    free(temp);
    return days;
}

// Function to run a single test case
void runTestCase(const int* input, int size, int expected, const char* description) {
    // Create a copy of input array
    int* testInput = (int*)malloc(size * sizeof(int));
    if(testInput == NULL) {
        printf("Memory allocation failed!\\n");
        exit(1);
    }
    memcpy(testInput, input, size * sizeof(int));

    int result = minimumDays(size, testInput);

    printf("\\nTest Case: %s\\n", description);
    printf("Input: ");
    for(int i = 0; i < size; i++) {
        printf("%d", input[i]);
        if(i < size - 1) printf(", ");
    }
    printf("\\nExpected: %d\\n", expected);
    printf("Got: %d\\n", result);
    printf("Status: %s\\n", (result == expected ? "PASSED ✓" : "FAILED ✗"));

    free(testInput);
}

// Function to run all test cases
void runAllTests() {
    printf("Running test cases...\\n");

    int test1[] = {3, 3};
    runTestCase(test1, 2, 1, "Case 1: Equal heights");

    int test2[] = {5, -3};
    runTestCase(test2, 2, 0, "Case 2: Already decreasing");

    int test3[] = {-1, 1, 1, 1};
    runTestCase(test3, 4, 3, "Case 3: Multiple days needed");
}

// Function to handle interactive input
void runInteractive() {
    int N;
    printf("Enter number of segments: ");
    scanf("%d", &N);

    int* L = (int*)malloc(N * sizeof(int));
    if(L == NULL) {
        printf("Memory allocation failed!\\n");
        exit(1);
    }

    for(int i = 0; i < N; i++) {
        printf("Enter height for segment %d: ", i + 1);
        scanf("%d", &L[i]);
    }

    int result = minimumDays(N, L);
    printf("\\nMinimum days needed: %d\\n", result);

    free(L);
}

int main() {
    // Run predefined test cases
    runAllTests();

    // Ask for interactive mode
    char choice;
    printf("\\nWould you like to run in interactive mode? (y/n): ");
    scanf(" %c", &choice);

    if(choice == 'y' || choice == 'Y') {
        runInteractive();
    }

    return 0;
}
    

This C implementation includes several important features and considerations:

• Memory Management:
  • Careful allocation and deallocation of dynamic arrays
  • Use of malloc and free
  • Memory error checking
  • Use of memcpy for array copying
• Key Components:
  • Main algorithm in minimumDays
  • Helper function for checking strictly decreasing property
  • Test suite
  • Interactive input mode
  • Error handling

Algorithm Logic

The algorithm maintains the same logic:

• Base case checking
• Binary reduction (2^(d-1))
• Right-to-left height reduction
• Iterative improvement

Compilation Instructions

To compile and run the program, use the following commands:

gcc road_construction.c -o road_construction
./road_construction
    

Test Cases

The program handles all test cases:

• {3, 3} → 1 day
• {5, -3} → 0 days
• {-1, 1, 1, 1} → 3 days

Key Differences from Other Language Versions

• Manual memory management
• Use of pointers instead of arrays/vectors
• C-style boolean values
• More explicit error handling
• C-style string handling

Example C Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int minimumDays(int *arr, int size) {
    // Algorithm logic here
}

int main() {
    int arr[] = {-1, 1, 1, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Minimum days: %d\n", minimumDays(arr, size));
    return 0;
}
    

Infosys HackWithlnfy 2025