Укажите двоичный код на основе условий в постоянное время

Question

Формулировка задачи: для двух целых чисел t и l задайте двоичный код длины l, такой, чтобы у нас были биты со значением 1 на каждые (t-1) бит в постоянное время.

Например, учитывая t= 3 и l = 10, результат равен 1001001001.

Решение, которое я могу придумать, заключается в проведении некоторых сдвигов двоичного кода со значением 1:

A1=1 

A2=A1>>3

A3=A1>>(3x2)

result=A1||A2||A3

Однако это решениене эффективен.

Я хочу решить эту проблему в постоянное время.

Answer 1

Может быть, вам нужно что-то вроде этого:

public class SomeClass {
    public static void main(String args[]) {
        int l = 15;
        for(int t = 1; t < 10; ++t) {
            System.out.println(t + " " + l + " => " + toBinString(solve(t, l), l));
        }
    }
    public static String toBinString(int value, int length) {
        String s = "";
        for(int i = 0; i < length; ++i)
            s += (char)('0' + (value >> i & 1));
        return s;
    }
    public static int solve(int t, int l) {
        return ((1 << (l + t - 1)) - 1) / ((1 << t) - 1);
    }
}

Вывод:

1 15 => 111111111111111
2 15 => 101010101010101
3 15 => 001001001001001
4 15 => 001000100010001
5 15 => 000010000100001
6 15 => 001000001000001
7 15 => 100000010000001
8 15 => 000000100000001
9 15 => 000001000000001