How to find the minimum time taken to eat at least P apple ? Please Help me to optimize the code for this problem

Question

Hi please help me with optimized solution for this question. I am also attaching a potential solution below. I need help to optimize the code in java. The question is given below .

Question :

Varun's team participated in an eating competition at FoodContest in which they are asked to eat at least P apples. Varun's team consists of N members where a member i (1 <= i <= N ) takes Arr[i] minutes to eat a single apple. the task is to find the minimum time to eat at least P apples.

Note: A member can eat a apple any number of times.

Example

Sample Input:- n=4, p=10 , Arr[i] = {1 ,2 ,3 ,4}

Sample output: 6

Explanation:-

1st member will eat 6 apple , (ie, 1*6)

2nd member will eat 3 apple , (2*3)

3rd member will eat 2 apple , (3*2)

4th member will eat 1 apple , (4*1)

total = 12 ( total > p ) ie, team need atlest 6 min (minimum) to eat atleast 10 apples.

Sample Input:- n=7 ,p=7 , Arr[i] = { 1 ,1 ,1 ,1, 1, 1 ,1 }

Sample Output: 1

Constraints:-

1 <= N <= 10^5

1 <= Arr[i] <= 10

1 <= P <= 10^12

Code: (note: I need help to optimize this code also reduce Time Complexity )

import java.io.*; 
import java.util.*; 


class Main {
    public static void main (String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");    
        String[] input = br.readLine().split(" "); 

        int n = Integer.parseInt(str[0]);  
        long p = Long.parseLong(str[1]);  
        long [] arr = new long [n];

        long max = 1000000000000L ;

        for(int i=0; i<n; i++) 
        {
            arr[i] = Long.parseLong(input[i]); 
        }
        
        
        for(long j=1;j<=max;j++){
            long sum=0;
            for(int i=0;i<n;i++){
                long rem=j/arr[i];
                sum=sum+rem;
                if(sum>=p){
                    System.out.println(j);
                    return;
                } 
            }  
        }

    }
}

Answer 1

Say input is arr = {1, 2, 3, 4}, p = 60.

Start by calculating the least common denominator (LCD), which in this case is 12.

Now calculate, for each minute in a 12 minute period, how many apples will be eaten:

Time	0	1	2	3	4	5	6	7	8	9	10	11	12
Member 1	0	1	2	3	4	5	6	7	8	9	10	11	12
Member 2	0	0	1	1	2	2	3	3	4	4	5	5	6
Member 3	0	0	0	1	1	1	2	2	2	3	3	3	4
Member 4	0	0	0	0	1	1	1	1	2	2	2	2	3
Total	0	1	3	5	8	9	12	13	16	18	20	21	25

Create an array with the value from the last row, i.e. calculate this array:

int[] total = { 0, 1, 3, 5, 8, 9, 12, 13, 16, 18, 20, 21, 25 };

You don't need to store the intermediate per-member values. They are just shown above for clarity.

We now know that the team eats 25 apples per 12 minute period, so to eat a total of 60 apples, we need at least 2 full rounds. So we calculate:

full rounds = p / 25 = 60 / 25 = 2
apples left = p % 25 = 60 % 25 = 10
time taken = 2 * 12 = 24 minutes
apples eaten = 2 * 25 = 50

Now do a binary search of the calculated array for the remaining apples, choosing the next higher value if an exact match is not found. For the 10 apples remaining, that would be time = 6, total = 12.

Which means we need another 6 minutes to eat another 12 apples, for a total of 62 (50 + 12) apples eaten in 30 (24 + 6) minutes.

Result: 30 minutes.

Now good luck writing the code for this algorithm.