Md.
Nazmul Hossain 223002089
1. C++ compiler
{
"cmd" : ["g++ -std=c++14 $file_name -o $file_base_name && timeout 4s
./$file_base_name<inputf.in>outputf.in"],
"selector" : "source.c",
"shell": true,
"working_dir" : "$file_path"
}
2. String to int
for(int i=str.length()-1, j=1; i >=0 ; i--, j*=10){
if(('0' <= str[i]) && ('9' >= str[i])){
a = str[i]-48;
digit += (a*j);
}
}
3. gcd
lld gcd(int a, int b){
if (b == 0){
return a;
}
return gcd(b, a%b);
}
4. LCM
lld lcm(int a, int b){
return (a*b)/gcd(a, b);
}
5. Quick Sort
int partision(int* &arr, int st, int en) {
int pivot = arr[st];
int cnt=0;
for(int i=st+1; i<=en; i++){
if(pivot >= arr[i]){
cnt++;
}
}
int pIndex = st+cnt;
printf("pivot = %d\n", pIndex);
swap(arr[st], arr[pIndex]);
int i=st, j=en;
while(i < pIndex && j > pIndex){
while(arr[i] <= pivot && i<pIndex){
i++;
}
while(arr[j] > pivot && j>pIndex){
j--;
}
1|Page
Md. Nazmul Hossain 223002089
if(i < pIndex && j > pIndex){
swap(arr[i], arr[j]);
i++; j--;
}
}
return pIndex;
}
void quickSort(int* &arr, int st, int en){
if(st >= en){
return ;
}
int p = partision(arr, st, en);
quickSort(arr, st, p-1);
//for right partision;
quickSort(arr, p+1, en);
}
6. Substring
string substr (size_t pos, size_t len) const;
string r = s1.substr(3, 2)
7. String Reverse
reverse(s.begin(), s.end());
8. Longest consecutive ones in a binary string
std::string test(std::string text) {
int ctr = 0;
int result = 0;
for (int i = 0; i < text.size(); i++) {
if (text[i] == '0')
ctr = 0;
else {
ctr++;
result = std::max(result, ctr);
}
}
return std::to_string(result);
}
9. Longest Common Subsequence
int lcsRec(string &s1, string &s2, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (s1[m - 1] == s2[n - 1])
return 1 + lcsRec(s1, s2, m - 1, n - 1);
else
return max(lcsRec(s1, s2, m, n - 1), lcsRec(s1, s2, m - 1, n));
}
int lcs(string &s1, string &s2) {
int m = s1.size(), n = s2.size();
return lcsRec(s1, s2, m, n);
}
2|Page
Md. Nazmul Hossain 223002089
10. Shortest path
vector<int> shortestPathBFS(const vector<vector<int>>& graph, int start, int end) {
int numNodes = graph.size();
vector<int> distances(numNodes, INT_MAX);
vector<int> parent(numNodes, -1); // Store parent nodes for path reconstruction
queue<int> q;
distances[start] = 0;
q.push(start);
while (!q.empty()) {
int current = q.front();
q.pop();
if (current == end) {
break; // Found the end node, no need to continue
}
for (int neighbor : graph[current]) {
if (distances[neighbor] == INT_MAX) {
distances[neighbor] = distances[current] + 1;
parent[neighbor] = current;
q.push(neighbor);
}
}
}
// Reconstruct the path (if found)
vector<int> path;
if (distances[end] != INT_MAX) {
int current = end;
while (current != -1) {
path.push_back(current);
current = parent[current];
}
reverse(path.begin(), path.end()); // Reverse to get the correct order
}
return path;
}
11. Prefix Sum
#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the prefix sum of a vector
vector<int> calculatePrefixSum(const vector<int>& arr) {
int n = arr.size();
vector<int> prefixSum(n);
if (n == 0) {
return prefixSum; // Return an empty vector for an empty input
}
prefixSum[0] = arr[0];
for (int i = 1; i < n; ++i) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
3|Page
Md. Nazmul Hossain 223002089
return prefixSum;
}
// Function to calculate the sum of a subarray using prefix sums
int getSubarraySum(const vector<int>& prefixSum, int start, int end) {
if (start == 0) {
return prefixSum[end];
} else {
return prefixSum[end] - prefixSum[start - 1];
}
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
vector<int> prefixSum = calculatePrefixSum(arr);
cout << "Prefix Sum: ";
for (int num : prefixSum) {
cout << num << " ";
}
cout << endl;
// Example: Get the sum of subarray [2, 4] (3, 4, 5)
int start = 2;
int end = 4;
int subarraySum = getSubarraySum(prefixSum, start, end);
cout << "Sum of subarray [" << start << ", " << end << "]: " << subarraySum <<
endl;
return 0;
}
12. Circle
Half circle perimeter: 1/2 (2π r)
(x−x1)2+(y−y1)2=r2
13. Sieve
void sieveOfEratosthenes(int n) {
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) {
cout << i << " ";
}
}
cout << endl;
}
4|Page
Md. Nazmul Hossain 223002089
14. Prime 1-N (nlogn)
#include <iostream>
using namespace std;
const int N = 1e7 + 9;
int d[N];
int main() {
for (int i = 1; i < N; ++i) {
for (int j = i; j < N; j += i) {
d[j]++;
}
}
for (int i = 1; i <= 100; i++) {
if (d[i] == 2) {
cout << i << '\n';
}
}
return 0;
}
15.Formulas
5|Page
