Day 1 Practice Assessment 1.txt

D1P1

Problem Statement


Aakash is implementing a program that finds the first non-repeating element in an array of integers. 


The program should take an integer N as input, representing the size of the array, and then read N integers from the user as the array elements. Afterwards, it should identify and print the first non-repeating element in the array. If no such element exists, it should indicate that no non-repeating element was found.


Assist Aakash in the program.
Input format :

The first line of input consists of an integer N, representing the size of the array.

The second line consists of N space-separated integers representing the array elements.
Output format :

If a non-repeating element is found in the array, print the first non-repeating element.

Otherwise, print "No non-repeating element found."


Refer to the sample output for formatting specifications.
Code constraints :

1 ≤ N ≤ 20

0 ≤ array elements ≤ 100
Sample test cases :
Input 1 :

6
1 4 2 5 1 2

Output 1 :

4

Input 2 :

8
1 2 3 4 1 2 3 4

Output 2 :

No non-repeating element found.

Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 


Solution

import java.util.HashMap;
import java.util.Scanner;

public class FirstNonRepeatingElement {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] arr = new int[N];
        
        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }

        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        for (int num : arr) {
            if (frequencyMap.get(num) == 1) {
                System.out.println(num);
                return;
            }
        }

        System.out.println("No non-repeating element found.");
    }
}

------------------------------------------------------------------------------------------------------------------------------------

D1P2

Problem Statement



Given a sequence of numbers in an array A. The task is to break short the array such the twice minimum value in the array should be greater than the maximum value in the array. The number of values removed from the array should be minimal. The removal of elements from the array can be done from the start or from the end of the array as per the condition mentioned above.
Input format :

The first line contains a single integer n, which represents the number of integers in the list.

The second set of input contains n integers on n lines, which represents the list of elements.
Output format :

The output consists of a single integer, which represents the minimum number of elements that need to be removed from the list to make the remaining elements in the list satisfy the condition that the minimum element is at least half of the maximum element.


Refer to the sample output for formatting specifications.
Sample test cases :
Input 1 :

7
2 
4 
5 
6 
8 
9 
1

Output 1 :

3

Input 2 :

4
4
7
5
6

Output 2 :

0

Expected Time Complexity : O(1)
Expected Space Complexity : O(1)
Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 


Solution

import java.util.Scanner;

public class MinElementsToRemove {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] A = new int[n];

        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextInt();
        }

        int minRemovals = n;
        
        for (int left = 0; left <= n; left++) {
            for (int right = 0; right <= n - left; right++) {
                int[] subArray = new int[n - left - right];
                System.arraycopy(A, left, subArray, 0, n - left - right);
                
                if (subArray.length > 0) {
                    int min = Integer.MAX_VALUE;
                    int max = Integer.MIN_VALUE;
                    for (int num : subArray) {
                        if (num < min) min = num;
                        if (num > max) max = num;
                    }
                    if (2 * min > max) {
                        minRemovals = Math.min(minRemovals, left + right);
                    }
                }
            }
        }

        System.out.println(minRemovals);
    }
}

------------------------------------------------------------------------------------------------------------------------------------

D1P3

Problem Statement


Your company is organizing a team-building activity where you need to arrange employees into two distinct groups: one group for technical activities and the other for creative activities.


The arrangement must ensure that:


    Technical employees (represented by positive integers) and creative employees (represented by negative integers) are alternated.
    The relative order within each group should be preserved.
    You have a list of employees where each employee is represented by a unique integer (positive for technical and negative for creative).


Your task is to rearrange the list such that technical and creative employees are alternated while maintaining the order within each group.


Write a program to rearrange the employees' list based on the given conditions.


Example

Input 

6

1 2 3 -4 -1 4

Output 

1 2 3 -4 -1 4  -------> Input list

-4 1 -1 2 3 4  -------> Rearranged list


Explanation

Creative employees come first and are alternated with technical employees.

The relative order within the technical and creative groups is preserved.


Note: Here employee ID "0" represent technical employee.
Input format :

The first line consists of an integer N representing the number of employees.

The second line consists of an array of integers of size N where each integer represents an employee's ID.

Positive integers represent technical employees, and negative integers represent creative employees.
Output format :

The first line contains the elements of the original employee list before rearrangement.

The second line contains the elements of the employee list after rearrangement according to the given conditions.


Refer to the sample output for the formatting specifications.
Code constraints :

2 ≤ n ≤ 10

-100 ≤ employees ID ≤100
Sample test cases :
Input 1 :

6
1 2 3 -4 -1 4

Output 1 :

1 2 3 -4 -1 4 
-4 1 -1 2 3 4 

Input 2 :

10
-5 -2 5 2 4 7 1 8 0 -8

Output 2 :

-5 -2 5 2 4 7 1 8 0 -8 
-5 5 -2 2 -8 4 7 1 8 0 

Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 


Solution

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] employees = new int[N];

        for (int i = 0; i < N; i++) {
            employees[i] = scanner.nextInt();
        }

        List<Integer> technical = new ArrayList<>();
        List<Integer> creative = new ArrayList<>();

        for (int emp : employees) {
            if (emp > 0) {
                technical.add(emp);
            } else {
                creative.add(emp);
            }
        }

        System.out.print("Original List: ");
        for (int emp : employees) {
            System.out.print(emp + " ");
        }
        System.out.println();

        List<Integer> rearranged = new ArrayList<>();
        int techIndex = 0, creativeIndex = 0;
        boolean placeCreative = true;

        while (techIndex < technical.size() || creativeIndex < creative.size()) {
            if (placeCreative && creativeIndex < creative.size()) {
                rearranged.add(creative.get(creativeIndex++));
            }
            if (!placeCreative && techIndex < technical.size()) {
                rearranged.add(technical.get(techIndex++));
            }
            placeCreative = !placeCreative;
        }

        System.out.print("Rearranged List: ");
        for (int emp : rearranged) {
            System.out.print(emp + " ");
        }
        System.out.println();
    }
}


------------------------------------------------------------------------------------------------------------------------------------

D1P4

Problem Statement


A restaurant receives a series of food orders each day. Sometimes, multiple customers order the same dish. The restaurant manager wants to identify the first unique dish order of the day — the first dish that no other customer ordered. This will help the chef to prepare the dish as a special item for the day.


Write a program to help the restaurant manager find the first unique dish order from the list of orders.


Example 1:

Input: 

5

1 2 1 3 1

Output:

2

Explanation: The first unique dish code is 2.


Example 3:

Input

10

1 2 3 4 5 5 4 3 2 1

Output

-1

Explanation: Since no dish code occurs only once, the output is -1.
Input format :

The first line input consists of an integer N representing the number of orders received in a day.

The second line consists of an array of integers of size N, where each integer represents a code for each dish ordered by customers.
Output format :

The output displays an integer representing the code of the first unique dish order. If there is no unique dish, return -1.


Refer to the sample output for the formatting specifications.
Code constraints :

1 ≤ N ≤ 10

1 ≤ dish code ≤ 100
Sample test cases :
Input 1 :

5
1 2 1 3 1

Output 1 :

2

Input 2 :

6
9 4 9 6 7 4

Output 2 :

6

Input 3 :

10
1 2 3 4 5 5 4 3 2 1

Output 3 :

-1

Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 


Solution

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] orders = new int[N];

        for (int i = 0; i < N; i++) {
            orders[i] = scanner.nextInt();
        }

        HashMap<Integer, Integer> countMap = new HashMap<>();
        
        for (int dish : orders) {
            countMap.put(dish, countMap.getOrDefault(dish, 0) + 1);
        }

        int firstUnique = -1;
        for (int dish : orders) {
            if (countMap.get(dish) == 1) {
                firstUnique = dish;
                break;
            }
        }

        System.out.println(firstUnique);
    }
}

------------------------------------------------------------------------------------------------------------------------------------

D1P5

Problem Statement


Imagine you are a sales manager at a retail store, and you need to analyze the daily sales data to determine the maximum revenue you can achieve from any continuous period of K days.


Example 1


Input: 

4 2

100 200 300 400


Output: 

700


Explanation:

300 + 400 = 700, which is the maximum.


Example 2


Input:

4 4

100 200 300 400


Output:

1000


Explanation:

100 + 200 + 300 + 400 = 1000, which is maximum.
Input format :

The first line consists of the two integers N, and K, representing the total number of days and the number of consecutive days, respectively.

The second line consists of an array of integers where each element represents the daily sales revenue for each day.
Output format :

The output displays a single integer, which is the maximum revenue obtained from any continuous period of K days.


Refer to the sample output for the formatting specifications.
Code constraints :

2 ≤ N ≤ 10

1 ≤ K ≤ N

1 ≤ sales revenue ≤ 1000
Sample test cases :
Input 1 :

4 2
100 200 300 400

Output 1 :

700

Input 2 :

4 4 
100 200 300 400

Output 2 :

1000

Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 


Solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        int[] sales = new int[N];

        for (int i = 0; i < N; i++) {
            sales[i] = scanner.nextInt();
        }

        int maxRevenue = 0;
        for (int i = 0; i <= N - K; i++) {
            int currentSum = 0;
            for (int j = 0; j < K; j++) {
                currentSum += sales[i + j];
            }
            if (currentSum > maxRevenue) {
                maxRevenue = currentSum;
            }
        }

        System.out.println(maxRevenue);
    }
}


------------------------------------------------------------------------------------------------------------------------------------

D1P6

Problem statement


Given an array 'arr' with 'n' elements, the task is to rotate the array to the left by 'k' steps, where 'k' is non-negative.


Example:

'arr '= [1,2,3,4,5]

'k' = 1  rotated array = [2,3,4,5,1]

'k' = 2  rotated array = [3,4,5,1,2]

'k' = 3  rotated array = [4,5,1,2,3] and so on.


Sample Input 1: 

8

7 5 2 11 2 43 1 1

2

Sample Output 1:

2 11 2 43 1 1 7 5

Explanation of Sample Input 1:

Rotate 1 steps to the left: 5 2 11 2 43 1 1 7

Rotate 2 steps to the left: 2 11 2 43 1 1 7 5


Sample Input 2:

4

5 6 7 8

3

Sample Output 2:

8 5 6 7

Explanation of Sample Input 2:

Rotate 1 steps to the left: 6 7 8 5

Rotate 2 steps to the left: 7 8 5 6

Rotate 3 steps to the left: 8 5 6 7

Expected Time Complexity:

O(n), where ‘n’ is the size of the array ‘arr’ and ‘k’ is the number of rotations.
Input format :

The first line of input consists of the number of integers n.

The second line of input consists of n elements in the array separated by spaces.

The third line of input consists of the integer k.
Output format :

The output prints the rotated elements in the array separated by spaces.


Refer to the sample output for the formatting specifications.
Code constraints :

1 ≤ n ≤ 20

1 ≤ arr[i] ≤ 90

1 ≤ k ≤ 11
Sample test cases :
Input 1 :

8
7 5 2 11 2 43 1 1
2

Output 1 :

2 11 2 43 1 1 7 5 

Input 2 :

4
5 6 7 8
3

Output 2 :

8 5 6 7 

Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 

Solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        int k = scanner.nextInt();
        k = k % n;

        int[] rotatedArray = new int[n];
        for (int i = 0; i < n; i++) {
            rotatedArray[i] = arr[(i + k) % n];
        }

        for (int i = 0; i < n; i++) {
            System.out.print(rotatedArray[i] + " ");
        }
        System.out.println();
    }
}


------------------------------------------------------------------------------------------------------------------------------------

D1P7

Problem Statement


You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water.


Return the maximum amount of water a container can store. Use a two-pointer algorithm to solve the problem.


Note: Notice that you may not slant the container.


Example



Input: 

9

1 8 6 2 5 4 8 3 7


Output:

49


Explanation:

In this case, the maximum area of water (blue section) the container can contain is 49.
Input format :

The first line of input consists of the array height of length n.

The next line consists of n space-separated heights.
Output format :

The output returns the maximum amount of water a container can store.
Code constraints :

n == height.length

2 ≤ n ≤ 50

0 ≤ height[i] ≤ 104
Sample test cases :
Input 1 :

9
1 8 6 2 5 4 8 3 7

Output 1 :

49

Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 


Solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] height = new int[n];

        for (int i = 0; i < n; i++) {
            height[i] = scanner.nextInt();
        }

        int maxArea = 0;
        int left = 0;
        int right = n - 1;

        while (left < right) {
            int width = right - left;
            int minHeight = Math.min(height[left], height[right]);
            int area = width * minHeight;
            maxArea = Math.max(maxArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        System.out.println(maxArea);
    }
}


------------------------------------------------------------------------------------------------------------------------------------

D1P8

Problem Statement


Jamie is currently working on an array manipulation problem and is seeking your assistance. The objective is to rearrange an array of integers by relocating all zeros to the end while maintaining the original order of the non-zero elements.


Create a program for the same.
Input format :

The first line of input consists of an integer N, representing the size of the array.

The second line consists of N space-separated integers, representing the elements of the array.
Output format :

The output displays the modified array after relocating all zeros to the end, with elements separated by spaces. If there are no zeros, print the array as it is.


Refer to the sample output for formatting specifications.
Code constraints :

In this scenario, the test cases fall under the following constraints:

2 ≤ N ≤ 15

0 ≤ elements ≤ 100
Sample test cases :
Input 1 :

2
8 9

Output 1 :

8 9 

Input 2 :

8
0 2 0 4 6 0 8 7

Output 2 :

2 4 6 8 7 0 0 0 

Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 


Solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }

        int[] result = new int[N];
        int index = 0;

        for (int i = 0; i < N; i++) {
            if (arr[i] != 0) {
                result[index++] = arr[i];
            }
        }

        for (int i = index; i < N; i++) {
            result[i] = 0;
        }

        for (int i = 0; i < N; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }
}

------------------------------------------------------------------------------------------------------------------------------------


D1P9

Problem Statement


Consider an event where a log register is maintained containing the guest’s arrival and departure times. Given an array of arrival and departure times from entries in the log register, find the point when there were the most guests present at the event.


Note: If an arrival and departure event coincide, the arrival time is preferred over the departure time.


Example:

Input:

arrival = { 1, 2, 4, 7, 8, 12 }

departure = { 2, 7, 8, 12, 10, 15 }


Output: Maximum number of guests is 3, present at time 7


Explanation:

Maximum Overlapping Interval
Input format :

The first line of input contains an integer value 'n', representing the number of guests.

The second line of input consists of n integers representing the arrival time of each guest.

The third line of input is an integer value 'm', which represents the number of guests for departure.

The fourth line of input consists of m integers representing the departure time of each guest.
Output format :

The first line of the output displays the maximum number of guests present at any time.

The second line of the output displays the time when the maximum number of guests are present.


Refer to the sample output for the formatting specifications.
Code constraints :

1 ≤ n ≤ 10

1 ≤ m ≤ 10
Sample test cases :
Input 1 :

6
5 2 3 7 8 9
6
1 2 3 5 6 7

Output 1 :

2
1

Input 2 :

6
1 2 4 7 8 12
6
2 7 8 12 10 15

Output 2 :

7
3

Expected Time Complexity : O(1)
Expected Space Complexity : O(1)
Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 


Solution

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arrival = new int[n];
        for (int i = 0; i < n; i++) {
            arrival[i] = scanner.nextInt();
        }

        int m = scanner.nextInt();
        int[] departure = new int[m];
        for (int i = 0; i < m; i++) {
            departure[i] = scanner.nextInt();
        }

        findMaxGuests(arrival, departure);
    }

    public static void findMaxGuests(int[] arrival, int[] departure) {
        int t = Arrays.stream(departure).max().getAsInt();
        int[] count = new int[t + 2];

        for (int i = 0; i < arrival.length; i++) {
            for (int j = arrival[i]; j <= departure[i]; j++) {
                count[j]++;
            }
        }

        int max_event_tm = 0;

        for (int i = 0; i <= t; i++) {
            if (count[max_event_tm] < count[i]) {
                max_event_tm = i;
            }
        }
        System.out.println(max_event_tm);
        System.out.println(count[max_event_tm]);
    }
}

------------------------------------------------------------------------------------------------------------------------------------


D1P10

Problem Statement:


You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.


Return the max sliding window.


Example 1:

Input: n=8

nums = [1,3,-1,-3,5,3,6,7], k = 3

Output: [3,3,5,5,6,7]


Explanation:


Example 2:

Input:n=1

nums = [1], k = 1

Output: [1]
Input format :

The first line contains an integer n, the number of elements in the array.

The second line contains n space-separated integers, representing the elements of the array nums.

The third line contains an integer k, the size of the sliding window.
Output format :

A single line containing the space-separated integers representing the maximum sliding window.


Refer to the sample output for formatting specifications.
Code constraints :

1 ≤ n ≤ 100

1 ≤ nums[i] ≤ 100

1 ≤ k ≤ n
Sample test cases :
Input 1 :

8
1 3 -1 -3 5 3 6 7
3

Output 1 :

3 3 5 5 6 7 

Input 2 :

1
1
1

Output 2 :

1 

Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 

Solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        
        int[] result = maxSlidingWindow(nums, k);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        
        for (int i = 0; i < n; i++) {
            if (!deque.isEmpty() && deque.peek() == i - k) {
                deque.poll();
            }
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offer(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }
        
        return result;
    }
}

------------------------------------------------------------------------------------------------------------------------------------

D1P11

Problem Statement


Given a list of non-negative integers, find the minimum number of merge operations to make it a palindrome. A merge operation can only be performed on two adjacent elements. The result of a merge operation is that the two adjacent columns are replaced with their sum. 


To make any array a palindrome, we can simply apply the merge operation n-1 times, where n is the size of the array (because a single-element array is always palindromic, similar to a single-character string). In that case, the size of the array will be reduced to 1.


Example


Input:

4

6

1

3

7


Output:

1


Explanation:

The first input is the size of the array, followed by array elements [6, 1, 3, 7].

Merge 6 & 1, i.e., 6+1 = 7, and now it is 7 3 7, and it is a palindrome.
Input format :

The first line consists of an integer n which is the size of the array.

The next n lines consist of an integer each, representing the array elements.
Output format :

The output is a single integer value denoting the number of merge operations.


Refer to the sample output for the formatting specifications.
Code constraints :

0 < n < 100

1 < values < 105
Sample test cases :
Input 1 :

4
4 
2 
3 
1

Output 1 :

1

Input 2 :

4
4 
5 
6 
3

Output 2 :

2

Input 3 :

4
6
1
3
7

Output 3 :

1

Expected Time Complexity : O(1)
Expected Space Complexity : O(1)
Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 

Solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        
        System.out.println(minMergeOperations(arr));
    }

    public static int minMergeOperations(int[] arr) {
        int left = 0, right = arr.length - 1;
        int mergeCount = 0;

        while (left < right) {
            if (arr[left] == arr[right]) {
                left++;
                right--;
            } else if (arr[left] < arr[right]) {
                arr[left + 1] += arr[left];
                left++;
                mergeCount++;
            } else {
                arr[right - 1] += arr[right];
                right--;
                mergeCount++;
            }
        }
        return mergeCount;
    }
}

------------------------------------------------------------------------------------------------------------------------------------

D1P12

Problem Statement


You have planned your visits to a recreational park one year in advance. The days of the year on which you will visit the park are given as an integer array visitDays. Each day is an integer from 1 to 365. 


Membership passes for the park are sold in three different ways:

    A 1-day pass is sold for membershipCosts[0] dollars.
    A 7-day pass is sold for membershipCosts[1] dollars.
    A 30-day pass is sold for membershipCosts[2] dollars.


The passes allow that many days of consecutive park visits. For example, if you get a 7-day pass on day 2, you can visit the park for 7 days: 2, 3, 4, 5, 6, 7, 8. 


Return the minimum number of dollars you need to spend to cover all your planned park visits given in the list visitDays.


Example 


Input:

visitDays = {1, 4, 6, 7, 8, 20}

membershipCosts = {2, 7, 15}

Output: 

11

Explanation: 

Here is one way to buy passes that cover your visit plan:

On day 1, you buy a 1-day pass for membershipCosts[0] = $2, which covers day 1.

On day 3, you buy a 7-day pass for membershipCosts[1] = $7, which covers days 3, 4, ..., 9.

On day 20, you buy a 1-day pass for membershipCosts[0] = $2, which covers day 20.

In total, you spent $11 and covered all the days of your park visits.


Company Tags: Google, Microsoft
Input format :

The first line of input consists of an integer N, representing the number of days planned to visit the park.

The second line consists of N integers, each representing visiting days, in strictly increasing order.

The third line consists of three space-separated integers, representing the membership cost of 1-day, 7-day, and 30-day passes, respectively.
Output format :

The output prints the minimum number of dollars that need to be spent to cover all the planned park visits.


Refer to the sample output for formatting specifications.
Code constraints :

1 ≤ N ≤ 365

1 ≤ visiting days ≤ 365

1 ≤ membershipCosts[i] ≤ 1000
Sample test cases :
Input 1 :

6
1 4 6 7 8 20
2 7 15

Output 1 :

11

Input 2 :

12
1 2 3 4 5 6 7 8 9 10 30 31
2 7 15

Output 2 :

17

Note :
The program will be evaluated only after the “Submit Code” is clicked.
Extra spaces and new line characters in the program output will result in the failure of the test case. 


Solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] visitDays = new int[N];
        for (int i = 0; i < N; i++) {
            visitDays[i] = scanner.nextInt();
        }
        int[] membershipCosts = new int[3];
        for (int i = 0; i < 3; i++) {
            membershipCosts[i] = scanner.nextInt();
        }
        System.out.println(minCost(visitDays, membershipCosts));
    }

    public static int minCost(int[] visitDays, int[] membershipCosts) {
        int[] dp = new int[366];
        int j = 0;

        for (int i = 1; i <= 365; i++) {
            if (j < visitDays.length && visitDays[j] == i) {
                dp[i] = Math.min(dp[i - 1] + membershipCosts[0], dp[Math.max(0, i - 7)] + membershipCosts[1]);
                dp[i] = Math.min(dp[i], dp[Math.max(0, i - 30)] + membershipCosts[2]);
                j++;
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[365];
    }
}

------------------------------------------------------------------------------------------------------------------------------------