It contains curated list of all data stuctures and algorithm used in various competitive programming websites such as Leetcode, Codechef, Codeforces, AtCoder etc. These data structres are listed topicwise and new problems are added regularly.
- DSA Code Snippets
- 1. Array
- 2. Bit Manipulation
- 3. Custom Comparator
- 4. Data Structures
- 5. Grid and Matrix
- 6. Sorting
- 7. Binary Search
- 8. Linked List
- 9. Priority Queue
- 10. Dynamic Programming
- 11. Graphs
- 11.1. Can We Go From Source To Destination
- 11.2. Print Euler Tour
- 11.3. Breadth First Search
- 11.4. DFS - First and Last Order
- 11.5. Dijkstra's Algorithm
- 11.6. Lowest Common Ancestor
- 11.7. Number of Connected Components
- 11.8. Kruskal Algorithm - Minimum Spanning Tree
- 11.9. Euler path - Heirholzer Algorithm
- 11.10. Bipartite Graph
- 11.11. Bellman Ford Algorithm
- 11.12. Topological Sort
- 12. Recursion
- 13. Binary Trees
- 14. String
- 15. STL
- 16. Lambda Function
- 17. Heaps
- 18. Permutation
- 19. Mathematics
- 20. Prime Numbers
- 21. Base Conversion
- 22. GCD and LCM
- 23. Geometry
- 24. Mathematical Equations
- 25. Miscellaneous
int findKthLargest(vector<int>& A, int k) {
nth_element(begin(A), begin(A) + k - 1, end(A), greater<int>());
return A[k - 1];
}int maxSumSubarray (vector<int> A) {
int n = A.size();
int local_max = 0;
int global_max = -1e9;
for(int i = 0; i < n; i++) {
local_max = max(A[i], A[i] + local_max);
if(local_max > global_max) {
global_max = local_max;
}
}
return global_max;
}
void solve() {
int n;
cin >> n;
vector<ll> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
ll mx = maxSumSubArray(a);
cout << mx << "\n";
}// Array - 1 2 3 4 5 6 7 8 9
// Rotate array to left by 3 positions.
// 4 5 6 7 8 9 1 2 3
rotate(vec1.begin(), vec1.begin() + 3, vec1.end());
// Rotate array to right by 3 positions.
// 7 8 9 1 2 3 4 5 6
rotate(vec1.begin(), vec1.begin() - 3, vec1.end());auto it = find (V.begin(), V.end(), num);
// it - V.begin() will given index of given num [0-indexed]
V[it - V.begin()] = otherNum;vector<int> slicing(vector<int>& arr, int X, int Y){
auto start = arr.begin() + X;
auto end = arr.begin() + Y + 1;
vector<int> result(Y - X + 1);
copy(start, end, result.begin());
return result;
}unorder_set<int> s;
for(int i : vec) {
s.insert(i);
}
vec.assign(s.begin(), s.end());
sort(vec.begin(), vec.end());
Another Method: Slower than the above method
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());int main() {
int countCommon = 0;
int n = 6;
vector<int> vec1 = {1, 3, 5, 7, 8, 9};
int m = 7;
vector<int> vec2 = {1, 2, 3, 7, 9, 4, 8};
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
vector<int> v(vec1.size() + vec2.size());
auto it = set_intersection(vec1.begin(), vec1.end(),vec2.begin(), vec2.end(),v.begin());
cout << "Common Elements : " << it - v.begin() << "\n";
cout << "The elements are : ";
for ( auto st = v.begin(); st != it; ++st) {
cout << *(st) << " ";
}
}vector<string> V = {"One", "Two", "Three", "Four", "Five"};
unordered_set<string> S(V.begin(), V.end());
// Use Cases
// -> To find any particular element : S.count("word");
// -> To erase any particular element : S.erase("word");
// 705 LeetCode - Design HashSet// Given an array arr[] of size N and an integer K. The task is to find the minimum number of elements that should be removed, such that Amax-Amin<=K.
// After the removal of elements, Amax and Amin is considered among the remaining elements.
class Solution{
public:
int removals(vector<int>& arr, int k){
//Code here
sort(arr.begin(),arr.end());
int n=arr.size();
int res=INT_MIN;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if((arr[j]-arr[i])<=k)
{
res=max(res,j-i+1);
}
}
}
return n-res;
}
};
// Input: N = 9, K = 4
// arr[] = {1,3,4,9,10,11,12,17,20}
// Output: 5
// Explanation: Remove 1, 3, 4 from beginning
// and 17, 20 from the end.for(int i = 0; i < 32; i++) {
if(x & (1 << i)) {
// True if ith bit of x is set
}
}int setbitsCnt = __builtin_popcount(x);
long int setbitsCnt = __builtin_popcountl(x);
long long setbitsCnt = __builtin_popcountll(x);int num = 104;
// Unset the 6th bit (bits start from 0 index)
int pos = 6;
cout << "Before : " << bitset<8>(num) << "\n";
num &= (~(1 << pos));
cout << "After :: " << bitset<8>(num) << "\n";// Current permutation of bits
unsigned int v = 11;
// Next permutation of bits
unsigned int w;
unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
cout << "v : " << bitset<8>(v) << "\n";
cout << "w : " << bitset<8>(w) << "\n";unsigned int v = 43;
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
cout << v << "\n";
// Output - 64 (which is power of 2).int result = reduce(nums.begin(), nums.end(), 0, bit_or());void bitmasks() {
int n = 5;
vector<vector<int>> masks(1 << n, vector<int>()); // 32 ( 2 ^ 5)
// Traverse all masks
for(int mask = 0; mask < (1 << n); mask++) {
for(int i = 0; i < n; i++) {
if(mask & (1 << i)) {
masks[mask].push_back(i);
cout << mask << " mask has this bit on => " << i << "\n";
}
}
}
vector<vector<int>> submasks(1 << n, vector<int>());
// Traverse all submasks of masks
for(int mask = 1; mask < (1 << n); mask++) {
for(int submask = mask; submask; submask = (submask - 1) & mask) {
submasks[mask].push_back(submask);
cout << mask << " mask has this submask => " << submask << "\n";
}
}
}bool cmp(const pair<string, long> &p1, const pair<string, long> &p2)
{
if(p1.second!=p2.second)
return p1.second < p2.second;
return p1.first < p2.first;
}
sort(vect.begin(), vect.end(), cmp);void solve()
{
int n;
cin >> n;
vector<string> s(n);
for(int i = 0; i < n; i++) {
cin >> s[i];
}
sort(s.begin(), s.end(), [&](string x, string y) {
return count(x.begin(), x.end(), '1') < count(y.begin(), y.end(), '1');
});
for(int i = 0; i < n; i++) {
cout << s[i] << "\n";
}
}
// Input
// 5
// 10101
// 10000000
// 010101
// 00111111
// 11000000000
// Output
// 10000000
// 11000000000
// 10101
// 010101
// 00111111struct city {
string name;
int score, index;
};
int n;
bool comp(const city a, const city b) {
if(a.name != b.name) {
return a.name < b.name;
}
return a.score > b.score;
}
void solve() {
cin >> n;
vector<city> cities(n);
for(int i = 0; i < n; i++) {
cin >> cities[i].name >> cities[i].score;
cities[i].index = i + 1;
}
sort(cities.begin(), cities.end(), comp);
for(int i = 0; i < n; i++) {
cout << cities[i].index << "\n";
}
}
// Input
// 6
// khabarovsk 20
// moscow 10
// kazan 50
// kazan 35
// moscow 60
// khabarovsk 40
// Output
// 3
// 4
// 6
// 1
// 5
// 2
int main() {
int n = 7;
vector<int> a = {4, 8, 1, 3, 2, 9, 11};
vector<int> ind(n);
iota(ind.begin(), ind.end(), 0);
for(auto a: ind) {
cout << a << " ";
}
cout << "\n";
sort(ind.begin(), ind.end(), [&](int i, int j) {
return a[i] > a[j];
});
for(auto a: ind) {
cout << a << " ";
}
cout << "\n";
}#include<bits/stdc++.h>
using namespace std;
constexpr int MAX_SIDE = 1000;
int prefixSum2D[MAX_SIDE + 1][MAX_SIDE + 1];
int array2D[MAX_SIDE + 1][MAX_SIDE + 1];
void solve()
{
int N;
int Q;
cin >> N >> Q;
// read the 2D array
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> array2D[i][j];
}
}
// build the prefix sum array
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
prefixSum2D[i][j] = array2D[i][j]
+ prefixSum2D[i - 1][j]
+ prefixSum2D[i][j - 1]
- prefixSum2D[i - 1][j - 1];
}
}
for (int q = 0; q < Q; q++) {
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << prefixSum2D[x2][y2]
- prefixSum2D[x1-1][y2]
- prefixSum2D[x2][y1-1]
+ prefixSum2D[x1-1][y1-1] << '\n';
}
}
int main(void) {
solve();
}vector<int> initializeDiffArray(vector<int>& A){
int n = A.size();
vector<int> D(n + 1);
D[0] = A[0], D[n] = 0;
for (int i = 1; i < n; i++)
D[i] = A[i] - A[i - 1];
return D;
}
void update(vector<int>& D, int l, int r, int x) {
D[l] += x;
D[r + 1] -= x;
}
vector<int> getArray(vector<int>& A, vector<int>& D) {
vector<int> ans;
for (int i = 0; i < A.size(); i++) {
if (i == 0) {
A[i] = D[i];
}
else {
A[i] = D[i] + A[i - 1];
}
ans.push_back(A[i]);
}
return ans;
}
// LeetCode - Shifting Letters IIstruct FenwickTree {
vector<int> bit; // binary indexed tree
int n;
FenwickTree(int n) {
this->n = n + 1;
bit.assign(n + 1, 0ll);
}
void add(int idx, int val) {
for (++idx; idx < n; idx += idx & -idx)
bit[idx] += val;
}
void range_add(int l, int r, int val) {
add(l, val);
add(r + 1, -val);
}
int get(int idx) { //
int ret = 0;
for (++idx; idx > 0ll; idx -= idx & -idx)
ret += bit[idx];
return ret;
}
};Problems Chef and Queries
// Using Structure
struct UnionFind{
int num;
vector<int> rs, parent;
UnionFind(int n): num(n), rs(n, 1), parent(n, 0) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
return (x == parent[x] ? x : parent[x] = find(parent[x]));
}
bool same(int x, int y) {
return find(x) == find(y);
}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (rs[x] < rs[y]) swap(x, y);
rs[x] += rs[y];
parent[y] = x;
num--;
}
int size(int x) {
return rs[find(x)];
}
int countSets() const {
return num;
}
};
// Using class
class UnionFind {
private:
vector<int> id, rank;
int cnt;
public:
UnionFind(int cnt) : cnt(cnt) {
id = vector<int>(cnt);
rank = vector<int>(cnt, 0);
for (int i = 0; i < cnt; ++i) id[i] = i;
}
int find(int p) {
if (id[p] == p) return p;
return id[p] = find(id[p]);
}
int getCount() {
return cnt;
}
bool connected(int p, int q) {
return find(p) == find(q);
}
void connect(int p, int q) {
int i = find(p), j = find(q);
if (i == j) return;
if (rank[i] < rank[j]) {
id[i] = j;
} else {
id[j] = i;
if (rank[i] == rank[j]) rank[j]++;
}
--cnt;
}
};
// Union Find that also return the vector of size of components.
class UnionFind {
vector<int> id, size;
public:
UnionFind(int n) : id(n), size(n, 1) {
for (int i = 0; i < n; ++i) id[i] = i;
}
void connect(int a, int b) {
int x = find(a), y = find(b);
if (x == y) return;
id[x] = y;
size[y] += size[x];
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
vector<int> &getSizes() {
return size;
}
};#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int main()
{
ordered_set p;
p.insert(5);
p.insert(2);
p.insert(6);
p.insert(4);
// value at 3rd index in sorted array.
cout << "The value at 3rd index ::" << *p.find_by_order(3) << endl;
// index of number 6
cout << "The index of number 6::" << p.order_of_key(6) << endl;
// number 7 not in the set but it will show the index number if it was there in sorted array.
cout << "The index of number seven ::" << p.order_of_key(7) << endl;
return 0;
}Problems
#include <bits/stdc++.h>
using namespace std;
struct SuccinctIndexableDictionary {
size_t length;
size_t blocks;
vector< unsigned > bit, sum;
SuccinctIndexableDictionary() = default;
SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {
bit.assign(blocks, 0U);
sum.assign(blocks, 0U);
}
void set(int k) {
bit[k >> 5] |= 1U << (k & 31);
}
void build() {
sum[0] = 0U;
for(int i = 1; i < blocks; i++) {
sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
}
}
bool operator[](int k) {
return (bool((bit[k >> 5] >> (k & 31)) & 1));
}
int rank(int k) {
return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
}
int rank(bool val, int k) {
return (val ? rank(k) : k - rank(k));
}
};
template< typename T, int MAXLOG >
struct WaveletMatrix {
size_t length;
SuccinctIndexableDictionary matrix[MAXLOG];
int mid[MAXLOG];
WaveletMatrix() = default;
WaveletMatrix(vector< T > v) : length(v.size()) {
vector< T > l(length), r(length);
for(int level = MAXLOG - 1; level >= 0; level--) {
matrix[level] = SuccinctIndexableDictionary(length + 1);
int left = 0, right = 0;
for(int i = 0; i < length; i++) {
if(((v[i] >> level) & 1)) {
matrix[level].set(i);
r[right++] = v[i];
} else {
l[left++] = v[i];
}
}
mid[level] = left;
matrix[level].build();
v.swap(l);
for(int i = 0; i < right; i++) {
v[left + i] = r[i];
}
}
}
pair< int, int > succ(bool f, int l, int r, int level) {
return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f};
}
// v[k]
T access(int k) {
T ret = 0;
for(int level = MAXLOG - 1; level >= 0; level--) {
bool f = matrix[level][k];
if(f) ret |= T(1) << level;
k = matrix[level].rank(f, k) + mid[level] * f;
}
return ret;
}
T operator[](const int &k) {
return access(k);
}
// count i s.t. (0 <= i < r) && v[i] == x
int rank(const T &x, int r) {
int l = 0;
for(int level = MAXLOG - 1; level >= 0; level--) {
tie(l, r) = succ((x >> level) & 1, l, r, level);
}
return r - l;
}
// k-th(0-indexed) smallest number in v[l,r)
T kth_smallest(int l, int r, int k) {
assert(0 <= k && k < r - l);
T ret = 0;
for(int level = MAXLOG - 1; level >= 0; level--) {
int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l);
bool f = cnt <= k;
if(f) {
ret |= T(1) << level;
k -= cnt;
}
tie(l, r) = succ(f, l, r, level);
}
return ret;
}
// k-th(0-indexed) largest number in v[l,r)
T kth_largest(int l, int r, int k) {
return kth_smallest(l, r, r - l - k - 1);
}
// count i s.t. (l <= i < r) && (v[i] < upper)
int range_freq(int l, int r, T upper) {
int ret = 0;
for(int level = MAXLOG - 1; level >= 0; level--) {
bool f = ((upper >> level) & 1);
if(f) ret += matrix[level].rank(false, r) - matrix[level].rank(false, l);
tie(l, r) = succ(f, l, r, level);
}
return ret;
}
// count i s.t. (l <= i < r) && (lower <= v[i] < upper)
int range_freq(int l, int r, T lower, T upper) {
return range_freq(l, r, upper) - range_freq(l, r, lower);
}
// max v[i] s.t. (l <= i < r) && (v[i] < upper)
T prev_value(int l, int r, T upper) {
int cnt = range_freq(l, r, upper);
return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);
}
// min v[i] s.t. (l <= i < r) && (lower <= v[i])
T next_value(int l, int r, T lower) {
int cnt = range_freq(l, r, lower);
return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);
}
};
int main()
{
const int n = 7;
vector<int> A(n);
for(auto &a : A) cin >> a;
WaveletMatrix<int, n> mat(A);
auto ans = mat.kth_smallest(0, 4, 3);
cout << "Kth smallest element in range [L, R) : " << ans << "\n";
auto rangefreq = mat.range_freq(0, n, 5);
cout << "Frequency of element in range [L, R) : " << rangefreq << "\n";
auto kthmax = mat.kth_largest(0, n, 2);
cout << "Kth Largest Element in Vector : " << kthmax << "\n";
}vector<int> height, lazy;
void push_up(int i) {
height[i] = max(height[i*2], height[i*2+1]);
}
void push_down(int i) {
if (lazy[i]) {
lazy[i*2] = lazy[i*2+1] = lazy[i];
height[i*2] = height[i*2+1] = lazy[i];
lazy[i] = 0;
}
}
void update(int i, int l, int r, int L, int R, int val) {
if (L <= l && r <= R) {
height[i] = val;
lazy[i] = val;
return;
}
push_down(i);
int mid = l + (r-l)/2;
if (L < mid) update(i*2, l, mid, L, R, val);
if (R > mid) update(i*2+1, mid, r, L, R, val);
push_up(i);
}
int query(int i, int l, int r, int L, int R) {
if (L <= l && r <= R) return height[i];
push_down(i);
int res = 0;;
int mid = l + (r-l)/2;
if (L < mid) res = max(res, query(i*2, l, mid, L, R));
if (R > mid) res = max(res, query(i*2+1, mid, r, L, R));
return res;
}Code
struct TrieNode {
TrieNode *next[26] = {};
bool isWord = false;
};
class Trie {
TrieNode root;
TrieNode* find(string s) {
auto node = &root;
for(char c : s) {
if(!node->next[c - 'a']) return NULL;
node = node->next[c - 'a'];
}
return node;
}
public:
void insert(string word) {
auto node = &root;
for(char c : word) {
if(!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
node = node->next[c - 'a'];
}
node->isWord = true;
}
bool search(string word) {
auto wordFind = find(word);
return wordFind && wordFind->isWord == true;
}
bool startsWith(string prefix) {
return find(prefix);
}
};int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
for (auto &dir : dirs) {
int a = x + dir[0], b = y + dir[1];
// Here x and y is our current location.
}
int dirs[8][2] = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
for (auto &dir : dirs) {
int a = x + dir[0];
int b = y + dir[1];
}int dirs[8][2] = {{-2,1}, {-1,2}, {1,2}, {2,1}, {2,-1}, {1,-2}, {-1,-2}, {-2,-1}};
for (auto &dir : dirs) {
int a = x + dir[0], b = y + dir[1];
// Here x and y is our current location.
}int M = 5, N = 3;
cout << "Lower Triangle Diagonals" << "\n";
for (int i = 0; i < M; ++i) {
cout << "------\n";
for (int x = i, y = 0; x < M && y < N; ++x, ++y) {
cout << x << " " << y << "\n";
}
}
cout << "-------\n";
cout << "Upper Triangle Diagonals" << "\n";
for (int j = 1; j < N; ++j) {
vector<int> v;
cout << "------\n";
for(int x = 0, y = j; x < M && y < N; ++x, ++y) {
cout << x << " " << y << "\n";
}
}int maximalSquare(vector<vector<char>>& matrix) {
int M = matrix.size();
int N = matrix[0].size();
int ans = 0;
vector<vector<int>> mat(M, vector<int>(N));
for(int i = 0; i < M; i++) {
for(int j = 0; j < N; j++) {
mat[i][j] = matrix[i][j] - '0';
}
}
for(int i = 0; i < M; i++) {
for(int j = 0; j < N; j++) {
if(i > 0 && j > 0 && mat[i][j] != 0) {
mat[i][j] = min({mat[i][j - 1], mat[i - 1][j], mat[i - 1][j - 1]}) + 1;
}
ans = max(ans, mat[i][j]);
}
}
// For side of largest square
// return ans
// For area of largest square
return ans * ans;
}int box[9][9] = {};
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
box[i][j] = (i / 3 ) * 3+ (j / 3);
}
}
for(int i = 0; i < 9; i++) {
for(int j = 0;j < 9; j++) {
cout << box[i][j] << " ";
}
cout << "\n";
}
// Output
// 0 0 0 1 1 1 2 2 2
// 0 0 0 1 1 1 2 2 2
// 0 0 0 1 1 1 2 2 2
// 3 3 3 4 4 4 5 5 5
// 3 3 3 4 4 4 5 5 5
// 3 3 3 4 4 4 5 5 5
// 6 6 6 7 7 7 8 8 8
// 6 6 6 7 7 7 8 8 8
// 6 6 6 7 7 7 8 8 8class Solution {
ListNode* splitList(ListNode *head) {
ListNode dummy, *p = &dummy, *q = &dummy;
dummy.next = head;
while (q && q->next) {
q = q->next->next;
p = p->next;
}
auto next = p->next;
p->next = NULL;
return next;
}
ListNode *mergeList(ListNode *a, ListNode *b) {
ListNode head, *tail = &head;
while (a && b) {
ListNode *node;
if (a->val <= b->val) {
node = a;
a = a->next;
} else {
node = b;
b = b->next;
}
tail->next = node;
tail = node;
}
if (a) tail->next = a;
if (b) tail->next = b;
return head.next;
}
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
auto b = splitList(head);
return mergeList(sortList(head), sortList(b));
}
};int L = 0, R = nums.size() - 1, pivot;
while (L < R) {
int M = L + (R - L) / 2;
if (nums[M] < nums[R]) R = M;
else L = M + 1;
}
pivot = L;int M = (L + R) / 2;
// signed integer overflow: 1063376696 + 2126753390 cannot be represented in type 'int'
int M = L + (R - L) / 2
// This will prevent overflowing.struct ListNode {
};
ListNode head, *tail = &head;
// Manipulate tail node here
return head.next;
// LeetCode - Merge Nodes In Between Zerosint getLength(ListNode* head) {
int length = 0;
for(; head; head = head->next, length++);
return length;
}ListNode* reverseList(ListNode* head) {
ListNode *prev = new ListNode();
while(head) {
auto node = head;
head = head->next;
node->next = prev->next;
prev->next = node;
}
return prev->next;
}auto cmp = [&](int a, int b){ return cnt[a] > cnt[b]; };
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
// Here cnt stores the frequency of elements given in vector.
// LeetCode - Sort Array By Increasing Frequency
// LeetCode - Merge K Sorted Lists
// LeetCode - Sort Characters By Frequency
// LeetCode - Top K Frequent Elements
// LeetCode - Top K Frequent Words
// LeetCode - Reduce Array Size To Halfclass Cmp {
public:
bool operator() (const pair<int, int>& a, const pair<int, int>& b) const {
return a.second < b.second;
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp> q(m.begin(), m.end()); // Assume there is an `m` storing pairs of `value, frequency`.typedef tuple <int, int, int> Item;
priority_queue<Item, vector<Item>, greater<>> pq;
// Getting items from tuple
int ele = get<0>(pq.top());
int a = get<1>(pq.top());
int b = get<2>(pq.top());int LIS(vector<int> &a) {
int n = a.size();
vector<int> dp(n, 1e9);
for(int i = 0; i < n; i++) {
auto it = lower_bound(dp.begin(), dp.end(), a[i]);
*it = a[i];
}
return lower_bound(dp.begin(), dp.end(), 1e9) - dp.begin();
}int N = A.size();
vector<int> pre(N + 1);
partial_sum(begin(A), end(A), begin(pre) + 1);
// Or simply
for (int i = 0; i < N; ++i) pre[i + 1] = pre[i] + A[i];
// Given an infinite supply of each denomination of Indian currency { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 } and a target value N.
// Find the minimum number of coins and/or notes needed to make the change for Rs N. You must return the list containing the value of coins required.
//{ Driver Code Starts
// Initial Template for C++
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
// User function Template for C++
class Solution{
public:
vector<int> minPartition(int N)
{
vector<int> arr = {1,2,5,10,20,50,100,200,500,2000};
vector<int> ans;
long long last = arr.size() - 1;
while(last >= 0){
if(arr[last] <= N){
N = N - arr[last];
ans.push_back(arr[last]);
}
else{
last --;
}
}
return ans;
}
};
//{ Driver Code Starts.
int main(){
int t;
cin>>t;
while(t--){
int N;
cin>>N;
Solution ob;
vector<int> numbers = ob.minPartition(N);
for(auto u: numbers)
cout<<u<<" ";
cout<<"\n";
}
return 0;
}
// } Driver Code Ends
// Input: N = 43
// Output: 20 20 2 1
// Explaination:
// Minimum number of coins and notes needed
// to make 43.
vector<int> G[100];
vector<bool>seen;
void dfs(int v) {
seen[v] = true;
for (auto next_v : G[v]) {
if (seen[next_v]) continue;
dfs(next_v);
}
}
void solve() {
int N, M,s,t;
cin >> N >> M >> s >> t;
for (int i = 1; i <=M; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
}
seen.assign(100, false);
dfs(s);
if (seen[t]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}vector<int> adj[1000];
int vis[1000];
int Euler[2000];
void eulerTree(int u, int &indx)
{
vis[u] = 1;
Euler[indx++] = u;
for (auto it : adj[u]) {
if (!vis[it]) {
eulerTree(it, indx);
Euler[indx++] = u;
}
}
}
void printEulerTour(int root, int N)
{
int index = 0;
eulerTree(root, index);
for (int i = 0; i < (2*N-1); i++)
cout << Euler[i] << " ";
}
void solve() {
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++) {
int , v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
printEulerTour(1, n);
}void bfs()
{
int n, m;
cin>> n >> m;
vector<int> adj[n+1];
memset(adj, 0, sizeof adj);
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
// Source Vertex
int s = 1;
queue<int> q;
vector<bool> used(n+1);
vector<int> d(n+1), p(n+1);
q.push(s);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : adj[v]) {
if (!used[u]) {
used[u] = true;
q.push(u);
d[u] = d[v] + 1;
p[u] = v;
}
}
}
// Check if there is any path between source vertex and vertex u.
int u = 4;
if (!used[u]) {
cout << "No path!";
} else {
vector<int> path;
for (int v = u; v != -1; v = p[v])
path.push_back(v);
reverse(path.begin(), path.end());
cout << "Path: ";
for (int v : path)
cout << v << " ";
}
}
// Problems
// LeetCode : 1971. Find if Path Exists in Graphvector<int> G[100];
vector<int> first_order;
vector<int> last_order;
vector<bool>seen;
void dfs(int v, int& first_ptr, int& last_ptr) {
first_order[v] = first_ptr++;
seen[v] = true;
for (auto next_v : G[v]) {
if (seen[next_v]) continue;
dfs(next_v, first_ptr, last_ptr);
}
last_order[v] = last_ptr++;
}
void solve()
{
int N, M; cin >> N >> M;
for (int i = 1; i <=M; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
seen.assign(100, false);
first_order.resize(100);
last_order.resize(100);
int first_ptr = 0, last_ptr = 0;
dfs(0, first_ptr, last_ptr);
for (int v = 0; v < N; ++v)
cout << v << ": " << first_order[v] << ", " << last_order[v] << endl;
}const int N = 3e5 + 9;
int n, m;
vector<pair<int, int>> g[N];
// First parameter is source vertex and second is adjacency list
vector<long long> dijkstra(int s, vector<pair<int, int>> g[])
{
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
vector<long long> d(n + 1, 1e18); vector<bool> vis(n + 1, 0);
q.push({0, s});
d[s] = 0;
while(!q.empty()){
auto x = q.top(); q.pop();
int u = x.second;
if(vis[u]) continue; vis[u] = 1;
for(auto y: g[u]){
int v = y.first; long long w = y.second;
if(d[u] + w < d[v]){
d[v] = d[u] + w; q.push({d[v], v});
}
}
}
return d;
}
int u[N], v[N], w[N];
void solve()
{
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> u[i] >> v[i] >> w[i];
g[u[i]].push_back({v[i], w[i]});
g[v[i]].push_back({u[i], w[i]});
}
auto d1 = dijkstra(1, g);
auto d2 = dijkstra(5, g);
auto d3 = dijkstra(8, g);
for(int i = 1; i <= n; i++) {
cout << d1[i] << " ";
}
cout << "\n";
for(int i = 1; i <= n; i++) {
cout << d2[i] << " ";
}
cout << "\n";
for(int i = 1; i <= n; i++) {
cout << d3[i] << " ";
}
cout << "\n";
}
// Input
// 8 13
// 1 2 2
// 1 3 9
// 2 3 7
// 2 4 8
// 3 5 3
// 4 5 2
// 5 6 1
// 1 7 3
// 7 8 2
// 8 5 3
// 7 6 6
// 8 3 2
// 1 8 8
// Output
// 0 2 7 10 8 9 3 5
// 8 10 3 2 0 1 5 3
// 5 7 2 5 3 4 2 0 const int maxN = 2e5 + 1;
const int logN = 20;
int p[maxN][logN];
int timer, in[maxN], out[maxN];
vector<int> G[maxN];
void dfs(int u = 1, int par = 1) {
in[u] = ++timer;
p[u][0] = par;
for(int i = 1; i < logN; i++) {
p[u][i] = p[p[u][i-1]][i - 1];
}
for(int v: G[u]) {
if(v != par) {
dfs(v, u);
}
}
out[u] = ++timer;
}
bool ancestor(int u, int v) {
return in[u] <= in[v] && out[u] >= out[v];
}
int lca(int u, int v) {
if(ancestor(u, v)) return u;
if(ancestor(v, u)) return v;
for(int i = logN - 1; i >= 0; i--) {
if(!ancestor(p[u][i] , v)) {
u = p[u][i];
}
}
return p[u][0];
}
void solve()
{
int N, M, Q, x, y, a, b;
cin >> N >> M >> Q;
for(int i = 2; i <= N; i++) {
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs();
for(int q = 0; q < Q; q++) {
cin >> a >> b;
cout << lca(a, b) << "\n";
}
}
// Input
// 11 10 4
// 1 2
// 2 3
// 3 4
// 3 5
// 4 6
// 4 7
// 5 9
// 2 8
// 8 10
// 8 11
// 11 6
// 7 9
// 4 9
// 6 7
// Output
// 2
// 3
// 3
// 4vector<int> G[100];
vector<bool> seen;
void dfs(int v) {
seen[v] = true;
for (auto next_v : G[v]) {
if (seen[next_v]) continue;
dfs(next_v);
}
}
void solve()
{
int N, M; cin >> N >> M;
for (int i = 1; i <=M; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
int count = 0;
seen.assign(100, false);
for (int v = 1; v <=N; ++v) {
if (seen[v]) continue; // Through if v has been searched
dfs(v); // If v is unsearched, perform DFS starting from v
++count;
}
cout << count << endl;
}class UnionFind {
vector<int> id;
int size;
public:
UnionFind(int N) : id(N), size(N) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int p = find(a), q = find(b);
if (p == q) return;
id[p] = q;
--size;
}
bool connected(int a, int b) {
return find(a) == find(b);
}
int getSize() { return size; }
};
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& A) {
int N = A.size(), ans = 0;
vector<array<int, 3>> E;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) E.push_back({ abs(A[i][0] - A[j][0]) + abs(A[i][1] - A[j][1]), i, j });
}
make_heap(begin(E), end(E), greater<array<int, 3>>());
UnionFind uf(N);
while (uf.getSize() > 1) {
pop_heap(begin(E), end(E), greater<array<int, 3>>());
auto [w, u, v] = E.back();
E.pop_back();
if (uf.connected(u, v)) continue;
uf.connect(u, v);
ans += w;
}
return ans;
}
};
Problems
// LeetCode - Min Cost To Connect All Pairs
// LeetCode - Connecting Cities With Minimum Cost
// LeetCode - K Closest Points To Origin// LeetCode Problem - Valid Arrangement of Pairs
vector<vector<int>> validArrangement(vector<vector<int>>& E) {
int N = E.size();
unordered_map<int, vector<int>> G;
unordered_map<int, int> indegree, outdegree;
G.reserve(N);
indegree.reserve(N);
outdegree.reserve(N);
for (auto &e : E) {
int u = e[0], v = e[1];
outdegree[u]++;
indegree[v]++;
G[u].push_back(v);
}
int start = -1;
for (auto &[u, vs] : G) {
if (outdegree[u] - indegree[u] == 1) {
start = u; // If there exists one node `u` that `outdegree[u] = indegree[u] + 1`, use `u` as the start node.
break;
}
}
if (start == -1) start = E[0][0]; // If there doesn't exist such node `u`, use any node as the start node
vector<vector<int>> ans;
function<void(int)> euler = [&](int u) {
auto &vs = G[u];
while (vs.size()) {
int v = vs.back();
vs.pop_back();
euler(v);
ans.push_back({ u, v }); // Post-order DFS. The edge is added after node `v` is exhausted
}
};
euler(start);
reverse(begin(ans), end(ans)); // Need to reverse the answer array in the end.
return ans;
}bool isBipartite(vector<vector<int>>& G) {
vector<int> id(G.size());
function<bool(int, int)> dfs = [&](int u, int prev) {
if (id[u]) return id[u] != prev; // This node's part should be the same as the part of the previous part
id[u] = -prev; // Assign nodes to one of the two parts, -1 or 1
for (int v : G[u]) {
if (!dfs(v, id[u])) return false;
}
return true;
};
for (int i = 0; i < G.size(); ++i) {
if (id[i]) continue; // This node is already assigned to a part
if (!dfs(i, 1)) return false;
}
return true;
}vector<int> bellmanFord(vector<vector<int>>& edges, int V, int src) {
vector<int> dist(N, INT_MAX);
dist[src] = 0;
for (int i = 1; i < V; ++i) { // try to use all the edges to relax for V-1 times.
for (auto &e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] == INT_MAX) continue;
dist[v] = min(dist[v], dist[u] + w); // Try to use this edge to relax the cost of `v`.
}
}
return dist;
}Code
vector<int> topologicalSort(int k, vector<vector<int>> &A) {
vector<int> deg(k, 0), order; // Degree
vector<vector<int>> G(k, vector<int>(0));// Creation of graph
for(auto &c : A) {
int u = c[0], v = c[1];
G[u - 1].push_back(v - 1);
deg[v - 1]++;
}
queue<int> q;
for(int i = 0; i < k; i++) {
if(deg[i] == 0) {
q.push(i);// Push node with indegree zero.
}
}
while(q.size()) {
int x = q.front();
q.pop();
order.push_back(x + 1);
for(int &u : G[x]) {
if(--deg[u] == 0) {
q.push(u);
}
}
}
return order;
}int maxDigitInNumber(int n) {
if(n < 10) return n;
return max( maxDigitInNumber(n / 10), n % 10);
}// It will store the path in vector passed to this function.
bool findPath(TreeNode *node, TreeNode *target, vector<TreeNode*> &path) {
if (!node) return false;
path.push_back(node);
if (node == target) return true;
if (findPath(node->left, target, path) || findPath(node->right, target, path)) return true;
path.pop_back();
return false;
}stringstream ss;
ss << "Kiranpal Singh";
cout << ss.str() << "\n";
// We can also extract words from a string, perform some operation on each word
stringstream ss(sentence);
string word, ans;
while(ss >> word) {
ans += performOperation(word) + " ";
}
// https://leetcode.com/problems/apply-discount-to-prices/string s,t;
//t -> text s-> pattern
vector<int> rabin_karp(string const& s, string const& t) {
const int p = 31;
const int m = 1e9 + 9;
int S = s.size(), T = t.size();
vector<long long> p_pow(max(S, T));
p_pow[0] = 1;
for (int i = 1; i < (int)p_pow.size(); i++)
p_pow[i] = (p_pow[i-1] * p) % m;
vector<long long> h(T + 1, 0);
for (int i = 0; i < T; i++)
h[i+1] = (h[i] + (t[i] - 'a' + 1) * p_pow[i]) % m;
long long h_s = 0;
for (int i = 0; i < S; i++)
h_s = (h_s + (s[i] - 'a' + 1) * p_pow[i]) % m;
vector<int> occurences;
for (int i = 0; i + S - 1 < T; i++) {
long long cur_h = (h[i+S] + m - h[i]) % m;
if (cur_h == h_s * p_pow[i] % m)
occurences.push_back(i);
}
return occurences;
}
void solve()
{
cin >> t >> s;
ll n = s.length();
// Prints the vector of indices where pattern is matched in text.
auto a = rabin_karp(s, t);
for(auto &ele: a) {
cout << ele << " ";
}
cout << "\n";
}
//Input
// abcdeaabcfgabc abc
// Output
// 0 6 11string s = "01010011";
for(char &c : s) {
c ^= '0' ^ '1';
}
cout << "s: " << s << "\n";
// s: 10101100
// Problems
// CodeChef - K Flip (KLIP)vector<int> z_function(string s) {
int n = (int) s.length();
vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i <= r)
z[i] = min (r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return z;
}string addStr(const string& a, const string& b) {
int as = (int)a.size() - 1;
int bs = (int)b.size() - 1;
string res;
int carry = 0;
for (int i = 0;; ++i) {
int v = carry;
carry = 0;
if (i <= as) v += a[as-i] - '0';
if (i <= bs) v += b[bs-i] - '0';
if (v >= 10) {
v -= 10;
carry = 1;
}
if (i > as && i > bs && v == 0) break;
res.push_back(v + '0');
}
reverse(res.begin(), res.end());
return res;
}
void solve()
{
string a, b;
cin >> a >> b;
string ans = addStr(a, b);
cout << ans << "\n";
}
// Input
// 5555
// 4444
// Output
// 9999// Longest prefix which is also suffix
// The prefix and suffix should not overlap
vector<int> computeLPS(string t) {
int m = t.length();
vector<int> lps(m);
int i = 1, len = 0;
lps[0] = 0;
while (i < m) {
if (t[i] == t[len]) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
void solve()
{
string a, b;
cin >> a >> b;
auto A = computeLPS(a);
auto B = computeLPS(b);
for(auto &a: A) {
cout << a << " ";
}
cout << "\n";
for(auto &b: B) {
cout << b << " ";
}
cout << "\n";
}
// Input
// abcdabcdabcd
// abcdefabcdefabcdef
// Output
// 0 0 0 0 1 2 3 4 5 6 7 8
// 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12
vector< int > euler_phi_table(int n) {
vector< int > euler(n + 1);
for(int i = 0; i <= n; i++) {
euler[i] = i;
}
for(int i = 2; i <= n; i++) {
if(euler[i] == i) {
for(int j = i; j <= n; j += i) {
euler[j] = euler[j] / i * (i - 1);
}
}
}
return euler;
}
template< typename T >
T euler_phi(T n) {
T ret = n;
for(T i = 2; i * i <= n; i++) {
if(n % i == 0) {
ret -= ret / i;
while(n % i == 0) n /= i;
}
}
if(n > 1) ret -= ret / n;
return ret;
}
void EulerPhiDemo(int n) {
int countPhi = 0;
vector<int> whichNum;
for(int i = 0; i <= n; i++) {
if(gcd(i, n) == 1) {
whichNum.push_back(i);
countPhi++;
}
}
cout << "Euler Phi of " << n << " : " << countPhi << "\n";
cout << "The numbers are : ";
for(auto &a: whichNum){
cout << a << " ";
}
cout << "\n";
}
void solve()
{
auto eulerTable = euler_phi_table(100);
for(auto &a: eulerTable) {
cout << a << " ";
}
cout << "\n";
auto eulerNumber = euler_phi(20);
cout << eulerNumber << "\n";
EulerPhiDemo(5);
EulerPhiDemo(11);
EulerPhiDemo(20);
}
// Output
// Euler Phi Table
// 0 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8
// 16 6 18 8 12 10 22 8 20 12 18 12 28
// 8 30 16 20 16 24 12 36 18 24 16 40
// 12 42 20 24 22 46 16 42 20 32 24
// 52 18 40 24 36 28 58 16 60 30 36
// 32 48 20 66 32 44 24 70 24 72 36
// 40 36 60 24 78 32 54 40 82 24 64
// 42 56 40 88 24 72 44 60 46 72 32
// 96 42 60 40
// Euler Phi Number
// 8
// Euler Phi Demo
// Euler Phi of 5 : 4
// The numbers are : 1 2 3 4
// Euler Phi of 11 : 10
// The numbers are : 1 2 3 4 5 6 7 8 9 10
// Euler Phi of 20 : 8
// The numbers are : 1 3 7 9 11 13 17 19 set<int> S;
int N = 6;
for(int i = 0; i < N; i++) {
int x; cin >> x;
if(S.insert(x).second) {
cout << "New Element is inserted :)" << "\n";
} else {
cout << "Element already exists :(" << "\n";
}
}
// Input = 1 2 3 4 2 5
// Output:
// New Element is inserted :)
// New Element is inserted :)
// New Element is inserted :)
// New Element is inserted :)
// Element already exists :(
// New Element is inserted :)// Void Lambda Function
function<void(int, int)> dfs = [&](int start, int goal) {
// Write your code here.
};int n = 6;
auto isPermutation = [&](const vector<int> &A)->bool{
vector<int> vis(n + 1, false);
for(auto x : A){
if(x <= 0 || x > n || vis[x])
return false;
vis[x] = true;
}
return true;
};
vector<int> A = {1, 2, 3, 4, 5, 1};
vector<int> B = {3, 4, 5, 6, 1, 2};
if(isPermutation(A)) {
cout << "Vector A is permutation" << "\n";
}
if(isPermutation(B)) {
cout << "Vector B is permutation" << "\n";
}// Minimum heap and Maximum heap
void solve()
{
priority_queue<int, vector<int>, greater<int> > minHeap;
priority_queue<int, vector<int> > maxHeap;
int n, x;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> x;
minHeap.push(x);
maxHeap.push(x);
}
auto a = minHeap;
while(!a.empty()) {
cout << a.top() << " ";
a.pop();
}
cout << "\n";
auto b = maxHeap;
while(!b.empty()) {
cout << b.top() << " ";
b.pop();
}
cout << "\n";
}
// Input
// 8
// 1 5 2 19 23 9 7 33
// Output
// 1 2 5 7 9 19 23 33
// 33 23 19 9 7 5 2 1 vector<array<int, 3>> E;
make_heap(begin(E), end(E), greater<array<int, 3>>());
pop_heap(begin(E), end(E), greater<array<int, 3>>());
// Now the smallest element in Heap is at the back of vector E.
auto [w, u, v] = E.back();
E.pop_back()Problems
void solve()
{
string s;
cin >> s;
sort(s.begin(), s.end());
do {
cout << s << "\n";
} while(next_permutation(s.begin(), s.end()));
}
// Input
// abcd
// Ouput
// abcd
// abdc
// acbd
// acdb
// adbc
// adcb
// bacd
// badc
// bcad
// bcda
// bdac
// bdca
// cabd
// cadb
// cbad
// cbda
// cdab
// cdba
// dabc
// dacb
// dbac
// dbca
// dcab
// dcba/* The Chicken McNugget Theorem states that for any two relatively prime positive
integers m and n, the greatest integer that cannot that cannot be written
in the form a*m + b *n for non-negative integers a, b is mn - m - n. */
bool chickenMcNuggetTheorem(int m, int n, int number) {
for(int i = 0; i <= 10; i++) {
int y = number - i * n;
if(y >= 0 && y % m == 0) {
return true;
}
}
return false;
}
bool chickenMcNuggetTheoremModified(int m, int n, int number) {
if(number >= n * (number % m)) {
return true;
} else {
return false;
}
}
void solve()
{
int t, n;
cin >> t;
while(t--) {
cin >> n;
if(chickenMcNuggetTheoremModified(11, 111, n)) {
cout << "YES" << "\n";
} else {
cout << "NO" << "\n";
}
}
}
// Input
// 3
// 33
// 144
// 69
// Output
// YES
// YES
// NO
// Returns sum of two numbers a and b with given base
int sumWithBase(string a, string b, int base)
{
int len_a, len_b;
len_a = a.size(); len_b = b.size();
string sum, s;
s = "";
sum = "";
int diff;
diff = abs(len_a - len_b);
for (int i = 1; i <= diff; i++) s += "0";
if (len_a < len_b) a = s + a;
else b = s + b;
int curr, carry = 0;
for (int i = max(len_a, len_b) - 1; i > -1; i--)
{
curr = carry + (a[i] - '0') + (b[i] - '0');
carry = curr / base;
curr = curr % base;
sum = (char)(curr + '0') + sum;
}
if (carry > 0) sum = (char)(carry + '0') + sum;
int ans = stoi(sum);
return ans;
}
void solve()
{
string a, b;
cin >> a >> b;
cout << sumABwithBase(a, b, 10);
}
// Input
// 11 12
// Output
// 23// We have to check the log N base to X is integer. We can check that with fmod.
// We can take X to be any number. For example 2, 3, 4 ...
bool isPowerOfTwo(int n) {
return fmod(log10(n) / log10(2), 1) == 0;
}
bool isPowerOfThree(int n) {
return fmod(log10(n) / log10(3), 1) == 0;
}
bool isPowerOfFour(int n) {
return fmod(log10(n) / log10(4), 1) == 0;
}// Given a number (n) and no. of digits (m) to represent the number, we have to check if we can represent n using exactly m digits in any base from 2 to 32.
class Solution {
public:
string baseEquiv(int n, int m){
for (int i=2; i<=32; i++){
if ( pow(i,m-1) > n ) continue;
if (pow(i,m) > n) return "Yes" ;
}
return "No" ;
}
};
// Input: n = 8, m = 3
// Output: No
// Explanation: Not possible in any base. // Given a positive number X. Find the largest Jumping Number which is smaller than or equal to X.
class Solution {
public:
#define ll long long
ll ans=0;
void fun(ll n, ll x){
if(n>x)return ;
ans=max(ans, n);
int ls=n%10;
ll nn=n;
if(ls==0){
nn=10*n+ls+1;
fun(nn, x);
}else if(ls==9){
nn=10*n+ls-1;
fun(nn, x);
}else{
nn=10*n+ls+1;
fun(nn, x);
nn=10*n+ls-1;
fun(nn, x);
}
}
long long jumpingNums(long long x) {
for(int i=0;i<=9;i++){
fun(i, x);
}
return ans;
}
};
// Input:
// X = 10
// Output:
// 10const ll MAXN = 1e7;
bool comp[MAXN + 10];
vector<ll> primeVec;
void sieveOfEratosthenes()
{
for(int i = 2; i <= MAXN; i++){
if(comp[i]) continue;
primeVec.pb(i);
for(int j = 2 * i; j <= MAXN; j += i){
comp[j] = true;
}
}
}
int L,R;
void solve()
{
// Implementation
sieveOfEratosthenes();
cin >> L >> R;
// For finding prime numbers in range L,R
ll rangeAns = (upper_bound(primeVec.begin(), primeVec.end(), R)
- upper_bound(primeVec.begin(), primeVec.end(), L));
cout << rangeAns;
}
// Input - > 1 100
// Output -> 25 (25 Prime numbers between 2 and 100 inclusive)int convertToDecimal(string s, int k) {
int ans = 0;
for(char x: s) {
ans *= k;
ans += x - '0';
} return ans;
}
int main(){
int k;
string a,b;
cin >> k >> a >> b;
int A = convertToDecimal(a, k);
int B = convertToDecimal(b, k);
cout << A*B << endl;
return 0;
}// Finding maximum gcd of two numbers a and b in range [L, R]
// in O(n) time instead of O(n ^ 2) time.
// cin >> L >> R;
int maxGCD = -1e9;
int operations = 0;
for(int i = L; i <= R; i++) {
for(int j = i + 1; j <= R; j++) {
maxGCD = max(maxGCD, int(gcd(i, j)));
operations++;
}
}
cout << maxGCD << "\n";
int modifiedOperations = 0;
for(int c = R; c > 0; c--) {
modifiedOperations++;
if((L + c - 1) / c < R / c) {
cout << c << "\n";
goto end;
}
}
end:;
cout << operations << "\n";
cout << modifiedOperations << "\n";
// Input
// 100 279
// Output
// 139
// 139
// 16110
// 141namespace Dirichlet {
const int T = 1e6 + 9;
long long phi[T];
gp_hash_table<long long, long long> mp;
long long dp[T], inv;
int sz, spf[T], prime[T];
void init() {
memset(spf, 0, sizeof spf);
phi[1] = 1; sz = 0;
for (int i = 2; i < T; i++) {
if (spf[i] == 0) phi[i] = i - 1, spf[i] = i, prime[sz++] = i;
for (int j = 0; j < sz && i * prime[j] < T && prime[j] <= spf[i]; j++) {
spf[i * prime[j]] = prime[j];
if (i % prime[j] == 0) phi[i * prime[j]] = phi[i] * prime[j];
else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
dp[0] = 0;
for(int i = 1; i < T; i++) dp[i] = dp[i - 1] + phi[i];
inv = 1; // g(1)
}
long long p_c(long long n) {
if (n % 2 == 0) return n / 2 * ((n + 1));
return (n + 1) / 2 * (n);
}
long long p_g(long long n) {
return n;
}
long long solve (long long x) {
if (x < T) return dp[x];
if (mp.find(x) != mp.end()) return mp[x];
long long ans = 0;
for (long long i = 2, last; i <= x; i = last + 1) {
last = x / (x / i);
ans += solve (x / i) * (p_g(last) - p_g(i - 1));
}
ans = p_c(x) - ans;
ans /= inv;
return mp[x] = ans;
}
}
// Find number of pairs (a, b) such that a <= b <= N and gcd(a, B) = X
int main() {
int n, x; cin >> n >> x;
cout << solve(n / x) << '\n';
}#define int long long
#define maxn 1500001
int phi[maxn];
int s_phi[maxn];
void pre()
{
int i,j;
for(i=1;i<maxn;i++)
phi[i] = i;
s_phi[1] = 1;
for(i=2;i<maxn;i++)
{
if(phi[i] == i)
{
for(j=i;j<maxn;j=j+i)
phi[j] = (phi[j]/i)*(i-1);
}
s_phi[i] = s_phi[i-1] + phi[i];
}
}
int func(int n)
{
if(n < maxn)
return s_phi[n];
int g;
int x = sqrt(n);
int sum = 0;
for(g=2;g<=x;g++)
{
sum = sum + func(n/g);
}
x = n/(x+1);
for(g=1;g<=x;g++)
sum = sum + s_phi[g]*(n/g - n/(g+1));
sum = n*(n+1)/2 - sum;
return sum;
}
// Find number of pairs (a, b) such that a <= b <= N and gcd(a, B) = X
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
pre();
//cin >> t;
while(t--){
int N, X;
cin >> N >> X;
cout << func(N/X);
}
}typedef double T;
struct pt {
T x, y;
pt operator+ (pt p) {
return {x + p.x, y + p.y};
}
pt operator- (pt p) {
return {x - p.x, y - p.y};
}
pt operator* (T d) {
return { x * d, y * d};
}
pt operator/ (T d) {
return {x/d, y/d};
}
};
bool operator==(pt a, pt b) {
return a.x == b.x && a.y == b.y;
}
bool operator!= (pt a, pt b) {
return !(a == b);
}
T sq(pt p) {
return p.x * p.x + p.y * p.y;
}
double abs(pt p) {
return sqrt(sq(p));
}
ostream& operator<< (ostream& os, pt p) {
return os << "(" << p.x << "," << p.y << ")";
}
void solve()
{
pt a, b;
cin >> a.x >> a.y >> b.x >> b.y;
cout << a+b << " " << a-b << "\n";
cout << a*-1 << " " << b/2 << "\n";
pt c;
cin >> c.x >> c.y;
cout << abs(c) << "\n";
}
// Input
// 3 4
// 2 -1
// -5 -10
// Output
// (5,3) (1,5)
// (-3,-4) (1,-0.5)
// 11.1803
void equation(int a, int b, int n) {
for (int i = 0; i * a <= n; i++) {
if ((n - (i * a)) % b == 0) {
cout << "x = " << i << ", y = " << (n - (i * a)) / b;
return;
}
}
cout << "No solution exists." << "\n";
}long long a = numeric_limits<long long>::max();
int b = numeric_limits<int>::max();int median(vector<int> &A) {
sort(A.begin(), A.end());
int N = A.size();
cout << "Size : " << N << "\n";
for(auto a : A) {
cout << a << " ";
}
cout << "\n";
if(N % 2 == 0) {
return A[(N - 2) / 2];
}
return A[(N - 1) / 2];
}int rev(int n) {
string s = to_string(n);
reverse(s.begin(), s.end());
return stoi(s);
}
int rev2(int x) {
int b = 0;
while (a > 0) {
b = b * 10 + (a % 10);
a /= 10;
}
return b;
}
int main()
{
int n = 988;
int m = 930;
cout << rev(n) << "\n";
cout << rev(m) << "\n";
}mt19937 rng{random_device{}()};
uniform_real_distribution<double> uni{0, 1};
// It will generate the random numbers every time in given range
// cout << uni(rng) << "\n";// One day Jim came across array arr[] of N numbers. He decided to divide these N numbers into different groups.
// Each group contains numbers in which sum of any two numbers should not be divisible by an integer K.
// Print the size of the group containing maximum numbers.
//{ Driver Code Starts
//Initial Template for C++
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//User function Template for C++
class Solution {
public:
int maxGroupSize(int a[], int n, int k) {
int count=0;
unordered_map<int,int> mp;
for(int i=0;i<n;i++){
mp[a[i]%k]++;
}
if(mp.find(0)!=mp.end()) mp[0]=1;
for(auto x:mp){
if(mp.find(k-x.first)!=mp.end()){
if(x.first==k-x.first) mp[x.first]=1;
count+=max(mp[k-x.first],mp[x.first]);
mp[k-x.first]=0;mp[x.first]=0;
}
else{
count+=mp[x.first];
mp[x.first]=0;
}
}
return count;
}
};
//{ Driver Code Starts.
int main() {
int t;
cin >> t;
while (t--) {
int N,K;
cin>>N>>K;
int arr[N];
for(int i=0; i<N; i++)
cin>>arr[i];
Solution ob;
cout << ob.maxGroupSize(arr,N,K) << endl;
}
return 0;
}
// Input:
// N = 4, K = 8
// arr[] = {1, 7, 2, 6}
// Output:
// 2Template
About Me