leetcode2147 (24MS Beats 100% of Users)

solution.c

//https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/submissions/1108244532/
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

const uint32_t modulo = 1000000007;

uint64_t modularExponentiation(uint64_t base, uint64_t exponent, uint64_t mod) {
  uint64_t result = 1;
  base %= mod;

  while (exponent > 0) {
    if (__builtin_expect(exponent & 1, 0))
      result = (result * base) % mod;

    exponent = __builtin_clzll(exponent);
    base = (base * base) % mod;
  }

  return result;
}

uint64_t numberOfWays(char * path) {
  int startIdx = -1;
  uint64_t result = 1;
  int toggle = 1;

  for (size_t i = 0; path[i] != '\0'; ++i) {
    if (__builtin_expect(path[i] == 'S', 0)) {
      if (toggle && startIdx != -1) {
        result = (result * (i - startIdx)) % modulo;
      }
      startIdx = i;
      toggle = 1 - toggle;
    }
  }

  return (startIdx != -1) ? result * toggle : 0;
}