Skip to content

Instantly share code, notes, and snippets.

View aakashns's full-sized avatar
🎯
Focusing

Aakash N S aakashns

🎯
Focusing
View GitHub Profile
@aakashns
aakashns / binomial_coefficients.cpp
Created June 13, 2012 17:41
Functions to calculate Binomial Coefficients modulo 1000000007
#define MAX 1000000007
#define FACT_MAX 250
int add(int a, int b){
return (a + b) % MAX;
}
int mul(int a, in b){
return ((long long)a * b) % MAX;
}
@aakashns
aakashns / binomial_coefficients2.cpp
Created June 13, 2012 18:07
Dynamic programming algorithm for calculating binomial coefficients
#define C_MAX 250
int C[C_MAX][C_MAX];
C[0][0] = 1;
for (int i = 1; i < C_MAX; i++){
C[i][0] = 1;
for (int j = 1; j <= i; j++){
/* Actual Binomial Coefficient */
//C[i][j] = C[i-1][j] + C[i-1][j-1];
@aakashns
aakashns / power_of_two.cpp
Created June 14, 2012 14:51
Function to determine if the given integer is a power of 2
bool is_power_of_two(int n){
return x && !(x & (x - 1));
}
@aakashns
aakashns / xor_swap.cpp
Created June 14, 2012 14:55
Swap integers using the XOR operator
void swap(int & a, int & b){
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
@aakashns
aakashns / snip2.cpp
Created June 18, 2012 17:41
Code snippet for 1's and 0's
int diff = 0;
for (int i = 0; i <= n; i++){
if (B[diff + n] == -1) B[diff + n] = i;
else B[diff+ n] = min(B[diff + n], i);
if (C[diff + n] == -1) C[diff + n] = i;
else C[diff + n] = max(C[diff + n], i);
if (i < n && A[i] == 0) diff--;
@aakashns
aakashns / union_find.cpp
Created June 19, 2012 17:38
Union Find
#include <iostream>
static const int N = 10000;
int main()
{ int i, j, p, q, id[N], sz[N];
for (i = 0; i < N; i++)
{ id[i] = i; sz[i] = 1; }
while (cin >> p >> q)
{
@aakashns
aakashns / opt_1s_0s.cpp
Created June 19, 2012 21:43
Optimized Code for 1's and 0's
int diff = 0;
for (int i = 0; i <= n; i++){
if (B[diff + n] == -1) B[diff + n] = i;
else C[diff + n] = i;
if (A[i]) diff++; else diff--;
}
@aakashns
aakashns / backtrack.c
Created June 22, 2012 00:49
Backtracking Implementation
int finished = 0; /* found all solutions yet? */
template <class T>
backtrack(int a[], int k, T * input)
{
T c[MAXCANDIDATES]; /* candidates for next position */
int ncandidates; /* next position candidate count */
int i; /* counter */
if (is_a_solution(a,k,input))
@aakashns
aakashns / prime_factorize.cpp
Created June 22, 2012 01:06
Prime Factorization of a Number
prime_factorization(long x)
{
long i; /* counter */
long c; /* remaining product to factor */
c = x;
while ((c % 2) == 0) {
printf("%ld\n",2);
c = c / 2;
}
@aakashns
aakashns / next_perm.cpp
Created June 22, 2012 02:00
Nest Permutation
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int * A = new int[n];
for (int i = 0; i < n; i++) A[i] = i + 1;