One or more planets to line up with the earth a certain amount of times

Question

I have attempted the below question, however my solution is too slow (i.e. It does not fit the 2 second time constrain for java). How can the solution be optimised?

While at IOI 2020 in Singapore, you decide to go outside one night and look up at the stars. At exactly midnight you observe a bright planet directly above you. Intrigued, you go inside and look up what this occurrence might have been on the internet. You are very surprised to learn that you have witnessed an extremely rare astronomical event! In fact, behind the planet you were seeing, there were (N − 1) more, and as it was directly overhead at midnight, these N (1 ≤ N ≤ 8) planets and Earth all exactly lined up with the sun!

This, however, was immediately followed by a significant disappointment as all news outlets were flooded by news that an alien civilization made contact with Earth with the information that, every time Earth and one or more of the N other planets line up precisely above the region of the Sun it was currently lined up above, the combined gravity causes instability in the core of the sun! In fact, during the K-th (1 ≤ K ≤ 10^16) such gravitational influence after this one, a solar flare will be released by the Sun destroying all life on Earth. Given the numbers N, K and the integer amount of years it takes for each of the N planets to orbit the Sun, your task is to calculate the year by which humans need to have a sustainable colony on another planet to avoid extinction (assume the Sun doesn’t rotate or burn up as time goes on). Note: In order to store the year the Sun destroys Earth, you might need to use a 64-bit datatype.

Input First line of input consists of two space-separated integers N and K, the numbers from the task. Next N lines of input consists of one integer ti, representing the time it takes for planet i to orbit around the Sun. This is guaranteed to be distinct and increasing.

Output should consist of one integer representing the year in which the Sun will destroy Earth.

For example, let N = 3, t = {2, 3, 4} and K = 9 The following will occur: • In year 2022, Planet 1 will line up with Earth

• In year 2023, Planet 2 will line up with Earth

• Similarly, in year 2024, Planets 1 and 3

• In year 2026, Planets 1 and 2]

• In year 2028, Planets 1 and 3

• In year 2029, Planet 2

• In year 2030, Planet 1

• In year 2032, Planets 1, 2 and 3

• In year 2034, Planet 1

standard output
Thus, in year 2034 the 9th occurrence will happen, and Earth will be destroyed.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class planets {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            long K= Long.parseLong(st.nextToken());
            long[] t = new long[N];
            
            st = new StringTokenizer(br.readLine());
            for (int index = 0; index < N; index++) {
                t[index] = (long) Long.parseLong(st.nextToken());
            }   

            long[] multiplyer = t.clone();
           
            while(K > 0){
                
                 
                long min = Long.MAX_VALUE;
                int index = -1;
            
                for (int i = 0; i < N; i++) {
                    if(multiplyer[i] < min){
                       min = multiplyer[i];
                        index = i;
                    }
                }

                multiplyer[index] += t[index];
           
                for (int i = 0; i < N; i++) {
                    if(multiplyer[i] == min){
                        multiplyer[i] += t[i];
                    }
                }
                
               K--;
            }
            long max = 0;
           
            for (int index = 0; index <  multiplyer.length; index++) {
                if ((multiplyer[index] - t[index] > max)) {
                    max = multiplyer[index] - t[index];
                    
                }
             
            }
            long years = max;
         
            System.out.println(Long.toString(2020 + years));
        }
    
       

}

Answer 1

Your code is well to read, in my opinion, some formatting is here and there off but otherwise it looks good. The code itself, I mean, I didn't validate the logic.

---

You should split your logic into two or three functions.

1. Reading the input.
2. Preparing the input.
3. The actual calculation.

In this case I guess it would be enough to have them as private static functions. A helper class yo hold all the parameters might be required in that case, though. Overall ideally your main-logic would look something like this:

public static void main(String[] args) {
    String inputLine = readInputLineFromUser();
    Parameters parameters = prepareParameters(inputLine);
    long year = calculateYear(parameters);
    
    System.out.println("Year: " + Long.toString(year));
}

Parameters could be a super-cheap and easy data holder (doesn't even need to be a POJO, I guess):

private static class Parameters {
    public long K;
    public long N;
    public long[] t;
}

Something like this. Though, not modifying these instances directly (as you currently do with the parameters) is advisable.

Additionally, having different functions for each step would allow you to easily add tests (of any sort) and test each functionality without having to go through each step. For example, right now if you want to know whether preparing of the parameters with the StringTokenizer works, you must start the program and type them in. If that is its own function you can always just call the method multiple times with your test-parameters.