1 / 2
Apr 2020

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;
	}
}

}

  • created

    Apr '20
  • last reply

    Apr '20
  • 1

    reply

  • 473

    views

  • 2

    users

  • 1

    link

I’ve modified your code to run the hardest, according to the constraints, imaginable testfile on BACTERIA3 and it came in at 0.33s so you’re close to getting the green bar. I’d recommend looking at possibilities to get rid of the back-and-forth between calculate() and getLast() and do it using single, simpler function.