[Codewar] Twice linear

https://www.codewars.com/kata/5672682212c8ecf83e000050/java

Codewars: Train your coding skills

 

Consider a sequence u where u is defined as follows:

1. The number u(0) = 1 is the first one in u.
2. For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too.
3. There are no other numbers in u.

Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on...

Task:

Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u (so, there are no duplicates).

Example:

dbl_linear(10) should return 22

Note:

Focus attention on efficiency

 

 

 

 

Solution

: idea는 set과 Treeset을 이용하는 것

: 계속해서 첫 요소를 지워가는 것

import java.util.SortedSet;
import java.util.TreeSet;

class DoubleLinear {
public static final int FIRST_NUM = 1;

    public static int dblLinear (int n) {
        int first = FIRST_NUM;
        SortedSet<Integer> list = new TreeSet<>();
        list.add(first);
        for(int i = 0; i<n; i++) {
            list.add(function1(list.first()));
            list.add(function2(list.first()));
            list.remove(list.first());
        }
        return list.first();
    }
    
    private static Integer function1(Integer a) { return (2*a)+1; }
    private static Integer function2(Integer b) { return (3*b)+1; }
}