Ch-sriram

print("Hello World!")

Ch-sriram

// Only works for 64 bit integers
int64_t pow2 (long long N) {
  if (N==0) return 1;
  return 1LL << N;
}

Ch-sriram

int setxy (int x, int y) {
  return ((1 << x) | (1 << y));
}

Ch-sriram

bool checkith (int N, int i) {
  return N & (1 << i);
  // Other solutions are:
  // return (N >> i) % 2;
  // return (N >> i) & 1;
}

Ch-sriram

// Refer checkith() function here: https://gist.github.com/Ch-sriram/fef3d0a6274d20f6705495b7cf5b22e4
bool checkith (long long N, int i) {
  return N & ((long long) 1 << i);
}

int countSetBits (long long N) {
  int count = 0;
  for (int i = 0; i < 64; ++i)
    if (checkith(N, i))
      ++count;

Ch-sriram

// for previous solution: https://gist.github.com/Ch-sriram/212f8185414fcb71278c6028128fcb2a

// Intuition behind the solution:
// When we apply bitwise-AND the number N with N-1, we get a new number whose Least Significant Set Bit is Unset. 

int countSetBits (long long N) {
  int cnt = 0;
  while (N != 0) {
    ++cnt;
    N = N & (N-1);  // This is the unsetting step.

Ch-sriram

// Naive Solution: O(N) Time Complexity
const long long M = (long long) 1e9+7;  // a very big prime number
long long pow(a, N) {
  if (N == 0) return 1;
  long long ans = 1;
  for(int i = 0; i < N; ++i)
    ans = ((ans % M) * a) % M;
  return ans % M;
}

Ch-sriram

// a^N using fast exponentiation
const int64_t M = (int64_t) 1e9+7;  // very big prime number

int64_t pow_fast (int64_t a, int64_t N) {
  int64_t ans = 1, x = a;
  while (N != 0) {
    if (N & 1)
      ans = ((ans % M) * x) % M;
    x = ((x % M) * x) % M;
    N >>= 1;

Ch-sriram

// Good explanation: https://www.purplemath.com/modules/factzero.htm
#include <bits/stdc++.h>
using namespace std;

uint64_t trailing_zeroes(uint64_t n) {
    uint64_t zeroes = 0;
    for(uint64_t i = 1ULL, factor = 5ULL; factor <= n; ++i, factor = pow(5, i))
        zeroes += (n / factor);
    return zeroes;
}

Ch-sriram

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

#define u uint64_t

// Good explanation: https://www.youtube.com/watch?v=p5gn2hj51hs
u gcd_euclid(u a, u b) { return b == 0 ? a : gcd_euclid(b, a%b); }
u _lcm(u a, u b, u gcd) { return (a*b)/gcd; }