Интересно, написано, что в среднем константа, а в худшем линейная

Я знаю

Но это бред

Почему?

перебрать же надо всё

Так можно сказать что любая hash функция линейная

там нет хэша

в неупорядоченном

ну я так понимаю

а в обычном set есть

Возможно ошибаюсь

Хотя нет, в обычном просто дерево

В обычном точно нет

Т.к. откуда у хэша log N

дерево

а хэш за константу вычисляется

хеш у нас в мепах

Однако там те же самые характеристики у функций

Похоже там вообще нет хешей

Нигде

Complexity Logarithmic in the size of the container.

https://en.cppreference.com/w/cpp/container/map/contains

Теперь мне стало интересно, какие контейнеры в c++ работают с хэшами?

Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (O(1) amortized, O(n) worst-case complexity).

Понятно

Худший случай всё сбивает

Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (O(1) amortized, O(n) worst-case complexity).

ага, именно так. там есть unordered_(set/map) и обычные.

https://en.cppreference.com/w/cpp/container/unordered_set

соотвественно одни под капотом — деревья, другие — хэш-таблицы

Похоже там вообще нет хешей

Как раз таки в unordered есть

соотвественно одни под капотом — деревья, другие — хэш-таблицы

Ну да, я это и хотел сказать

У дерева не может быть лимита

соотвественно одни под капотом — деревья, другие — хэш-таблицы

Да, теперь стало яснее

А у Hash может быть колизии

А у Hash может быть колизии

И поэтому линия

Поэтому O(N) может быть

Но в это считать – берд

Ну вот, всё понятно теперь

Т.к. тогда вообще 90% всех O(N) становятся O(N^2)

Сегодняшняя задачка просто огонь. Я час тупил в бинарные представления чисел чтобы увидеть паттерн наконец.

Сегодняшняя задачка просто огонь. Я час тупил в бинарные представления чисел чтобы увидеть паттерн наконец.

Короткое решение получилось?

Указано, что она на дп

Ой, не пугайте меня

Я от сегодняшней еле отошел

🤣

Короткое решение получилось?

Короткое не то слово, буквально 3 строки.

Я ещё не делал

ДПшечка, да.

Короткое не то слово, буквально 3 строки.

О, отлично

там просто рекурсивное соотношение очень простое и очень круто объясняется по смыслу (по крайней мере я себе его так объяснил)

так что удивительно, что я сразу не заметил это

а только после тупления

Ну в числе столько единиц, из скольких степеней двоек оно состоит

А вот связать с предыдущим числом, надо подумать

Наверное тоже стоит расписать ответы в строку

А вот связать с предыдущим числом, надо подумать

Не обязательно с предыдущим только, а то я тоже сперва в эту ловушку попался.

Наверное тоже стоит расписать ответы в строку

ага, прямо пару десятков чисел и посмотреть на них прищуренным взглядом

С уважением к дп)

Уловил связь, надо теперь реализовать

Уловил связь, надо теперь реализовать

огонь. очевидно у тебя быстрее получилось 👍

а смог эту связь человеческим языком объяснить?

ну можно потом, чтобы не спойлерить.

Сложновато)

4 строки

где-то перебрал)

Даже 5

https://leetcode.com/problems/counting-bits/discuss/656728/S-O(n)-DP-solution-using-bitwise-operations

Думаю тут можно упростить как-то

Но работает

Думаю тут можно упростить как-то

Любопытно. А какая идея за этим?

Любопытно. А какая идея за этим?

Когда начинаем перебирать числа, идущие вслед за очередной степенью двойки то количество единиц в них больше на 1, чем число единиц у этого числа минус то самое число, являющееся степень двойки, которую мы только что прошли.

Сложновато объяснил

Но вообще люди там предлагают решение проще

Да, нормальная тема. Моя идея была в том, что у всех четных чисел количество единиц то же, что и у чисел вдвое меньше, ну потому что умножение на 2 это сдвиг одного бита и все единички сдвинутся, но количество то же будет. А если нечетное, то можно отступить на шаг назад и станет четным, ну и плюс один, потому что если число стало нечётным с четного, то последний нолик сменился на 1

Это я понял благодаря последней подсказке когда тупил кучу времени уже на числами разными.

Это я понял благодаря последней подсказке когда тупил кучу времени уже на числами разными.

Да, это как раз самое простое решение

Но я не смотрел подсказки

Но я не смотрел подсказки

Молодец, отличное решение тогда. Я действую по своей схеме с первым звонком после ⏲

Молодец, отличное решение тогда. Я действую по своей схеме с первым звонком после ⏲

25 минут?

с помодоро