Leetcode взрывает моск. 326. Power of Three. Попытка оказаться в топе.

Очередная задача из категории Easy, которая превращается в совсем не "изи", как только мы пытаемся соблюсти ограничения. Но не всё ж считать количество учеников в классе.
https://leetcode.com/problems/power-of-three/description/

Нужно выяснить, является ли переданное число натуральной степенью тройки.
Ограничения: без циклов, без рекурсии, без хардкода всех степеней тройки в самой программе.
На вход подаётся 21040 чисел, и нужно, чтобы решение работало быстро.

Что перепробовано:

1) Взять 3¹⁹ (максимум, не превосходящий 2³¹) и поделить на входное число. Если остаток 0, то это - степень тройки, иначе - нет. Отрицательные числа и ноль отсеиваем отдельным условием.

12345678910

 class Solution {
private:
  static constexpr unsigned tt2 = 3u * 3u, tt6 = tt2 * tt2 * tt2,
                            tt18 = tt6 * tt6 * tt6, tt19 = tt18 * 3u;
 
public:
  bool isPowerOfThree(int n) {
    return n > 0 && !(tt19 % n);
  }
};

Лучшее время: 8 ms из 5 попыток.
Выглядит просто, но тысячи делений выполняются элементарно долго.

2) Хеш-таблица. При адресации младшими битами числа минимальный размер таблицы без коллизий - это 128. Усложнять хеш не стал, т.к. есть решение 3.

123456789101112131415161718

 class Solution {
private:
  static unsigned powers[128u];

public:
  bool isPowerOfThree(int n) {
    return n > 0 && powers[n & 127u] == n;
  }

  static void init() {
    unsigned a = 1u;
    powers[1] = a;
    for (unsigned char i = 1u; i <= 19u; i++) {
      a *= 3u;
      powers[a & 127u] = a;
    }
  }
};

Функцию init вызываем из статического инициализатора.
Лучшее время: 7 ms из 5 попыток.

3) Хеш-таблица с CLZ. В роли хеш-функции выступает инструкция CLZ (Count Leading Zeroes), доступная через соотв. интринсик. Пользуемся уникальностью битовой длины степеней тройки.

123456789101112131415161718

 class Solution {
private:
  static unsigned powers[31u];

public:
  bool isPowerOfThree(int n) {
    return n > 0 && powers[31u - __builtin_clz(n)] == n;
  }

  static void init() {
    unsigned a = 1u;
    powers[0] = a;
    for (unsigned char i = 1u; i <= 19u; i++) {
      a *= 3u;
      powers[31u - __builtin_clz(a)] = a;
    }
  }
};

Лучшее время: 3 ms из 8 попыток.

4) switch и хардкод, нарушение условия. Надеемся, что компилятор сотворит что-нибудь эдакое.

12345678910111213

 class Solution {
public:
  bool isPowerOfThree(int n) {
    switch (n) {
    case 1: case 3: case 9: case 27: case 81: case 243: case 729: case 2187: case 6561:
    case 19683: case 59049: case 177147: case 531441: case 1594323: case 4782969:
    case 14348907: case 43046721: case 129140163: case 387420489: case 1162261467:
      return true;
    default:
      return false;
    }
  }
};

Лучшее время: 4 ms из 7 попыток.

Везде включена оптимизация O3 (прагмой) и отключена синхронизация с stdio.

Думал ещё на тему признаков делимости на 3, но они позволяют проверить делимость только на 3. Для числа 15 будет положительный результат.

Индийские упражнения с вызовом функции log даже не беру в расчёт - полная глупость.

В топе вижу циклы с делением на 3. Это тоже нарушение условия, но работает шустро (компилятор заменяет деление на константу умножением, сдвигами и арифметикой).

Что тут ещё можно сделать?

Только авторизированные пользователи могут оставлять свои ответы

Дата

Популярность

resurce_inheit

Новичок

10мес

Без хардкода, рекурсий и циклов:

123456789

 class Solution { 
private: 
   static const int maxPowerOfThree = 1162261467; 
 
public: 
   bool isPowerOfThree(int n) { 
       return n > 0 && (maxPowerOfThree % n == 0); 
   } 
};

shi_143

Оракул

1г

12345678910111213141516171819202122

 class Solution { 
public: 
  bool isPowerOfThree(int n) { 
    // Проверяем, что число положительное 
    if (n <= 0) return false; 
    // Преобразуем число в строку в троичной системе счисления 
    string s = to_base3(n); 
    // Проверяем, что строка имеет вид 100...0, то есть начинается с 1 и содержит только нули после неё 
    return s[0] == '1' && s.find('1', 1) == string::npos; 
  } 
 
  // Функция для перевода числа в троичную систему счисления 
  string to_base3(int n) { 
    string res = ""; 
    while (n > 0) { 
      res = to_string(n % 3) + res; 
      n /= 3; 
    } 
    return res; 
  } 
};

Ответ удалён