I tried multiple things still getting TLE? Don’t know what am I missing? if any better methods are there please do tell…
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class Main
{
static List<Integer> list = new ArrayList<>();
public static void main(String[] args) {
init();
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i =0;i< t;i++) {
int input = sc.nextInt();
fibTester(input);
}
sc.close();
}
private static void fibTester(int input) {
List<Integer> l = calculate(input);
for(int i = l.size()-1;i>=0;i--) {
if(i!=0) {
System.out.print(l.get(i)+" ");
}else {
System.out.println(l.get(i));
}
}
}
public static List<Integer> calculate(int n) {
List<Integer> l = new ArrayList<>();
while(n> 0) {
int x = getLast(n);
l.add(x);
n -=x;
}
return l;
}
public static int getLast(int n) {
for(int i =list.size()-1;i>=0;i--) {
if(list.get(i)<=n) {
return list.get(i);
}
}
return -1;
}
public static void init() {
int high = (int) (Math.pow(10,8)+1);
int first = 0;
int second = 1;
int sum = 0;
while(sum< high) {
sum = first+second;
list.add(sum);
first = second;
second = sum;
}
}
}