Twice linear

kata programming

مساله:

دنباله u را در نظر بگیرید که به صورت زیر تعریف می شود:

  1. عبارت u(0) = 1 است
  2. برای هر x در u حتما عبارت های y = 2 * x + 1 و y = 3 * x + 1 را خواهیم داشت،
  3. هیچ عدد دیگری در u نیست

مثال:

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

شما باید n را به عنوان ورودی از تابع dbl_linear بگیرید و عددی را که در خانه n ام دنباله مرتب شده است برگرداند.

مثال:

dbl_linear(10) should return 22


Description:

Consider a sequence u where u is defined as follows:

The number u(0) = 1 is the first one in u.

For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too.

There are no other numbers in u.

Example:

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 sequence u (ordered with < so there are no duplicates) .

Example:

dbl_linear(10) should return 22

Note:

Focus attention on efficiency


import java.util.*;

class DoubleLinear {
    
    public static int dblLinear(int n) {
        if (n == 0) return 1;
        SortedSet<Integer> u = new TreeSet<>();
        u.add(1);
        for(int i=0; i<n; i++) {
            int x = u.first();
            u.add(x*2+1);
            u.add(x*3+1);
            u.remove(x);
        }
        return u.first();
    }
    
}
class DoubleLinear {
    
    public static int dblLinear (int n) {
        int[] nums = new int[n + 1];
        nums[0] = 1;
        int i = 0, j = 0, k = 1;
        while (k < n + 1) {
            int y = 2 * nums[i] + 1;
            int z = 3 * nums[j] + 1;
            if (y < z) {
                nums[k++] = y;
                i++;
            } else if (z < y) {
                nums[k++] = z;
                j++;
            } else {
                nums[k++] = z;
                i++;
                j++;
            }
        }
        return nums[n];
    }


}
import java.util.ArrayDeque;
import java.util.Deque;

public class DoubleLinear {
    
    public static int dblLinear (int n) {
        Deque<Integer>  deque2 = new ArrayDeque<Integer> ((int)n /2);
        Deque<Integer>  deque3 = new ArrayDeque<Integer> ((int)n /2);
        int cnt = 0, h = 1;
        while (true) {
            if (cnt >= n) return h;
            deque2.addLast(2 * h + 1);
            deque3.addLast(3 * h + 1);
            h = Math.min(deque2.peekFirst(), deque3.peekFirst());
            if (h == deque2.peekFirst())
                deque2.removeFirst();
            if (h == deque3.peekFirst())
                deque3.removeFirst();
            cnt++;
        }
    }
}
import java.util.*;
class DoubleLinear {
    
    public static int dblLinear (int n) {
        int pos = 0;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1); 

        while (pos <= (5*n) ){
            list.add(list.get(pos) * 2 + 1);
            list.add(list.get(pos) * 3 + 1);
            pos++;
        }
        

        Set<Integer> temp = new HashSet<>();
        temp.addAll(list);
        list.clear();
        list.addAll(temp);
        Collections.sort(list);
       
        return list.get(n);  
    }
}
import java.util.*;

class DoubleLinear {

    static List<Integer> done = new ArrayList<>();
    static Queue<Integer> result = new PriorityQueue<>(Arrays.asList(1));

    public static int dblLinear(int n) {
        int size = done.size();
        System.out.println(n);
        if (size >= n) {
            System.out.println("Vorgerechnet");
            return done.get(n);
        }
        int next = 0;
        for (int i = 0; i <= n - size; i++) {
            next = result.poll();
            done.add(next);
            int y = 2 * next + 1;
            int z = 3 * next + 1;
            if (!result.contains(y))
                result.add(y);
            if (!result.contains(z))
                result.add(z);
        }
        return next;
    }
}

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *