Missing number in array

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/// Raihan Ruhin (username : raihanruhin) /// Online resume: https://raihanruhin.github.io #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int main() { ios_base::sync_with_stdio(0), cin.tie(0); int tc, n, x; map<int, bool>mp; cin>>tc; while(tc--) { cin>>n; for(int i=1; i<n; i++) { cin>>x; mp[x]=true; } for(int i=1; i<=n; i++) if(!mp[i]) { cout<< i <<endl; break; } mp.clear(); } return 0; }

Kadane's Algorithm

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/// Raihan Ruhin (username : raihanruhin) /// Online resume: https://raihanruhin.github.io #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc, n, arr[1002], tmp, mx, ans; cin>>tc; while(tc--) { cin>>n; tmp = 0; ans = 0; mx = -1e9; //single max element of the array for(int i=0; i<n; i++) { cin>>arr[i]; mx = max(mx, arr[i]); tmp += arr[i]; tmp = max(tmp, 0); ans = max(ans, tmp); } if(ans==0) cout<<mx<<endl; else cout<<ans<<endl; } return 0; }

Army Buddies (UVa 12356, UVaLive 5789, Regionals 2011 >> Latin America)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

/// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int l[MX], r[MX]; int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc,kk=1, n, q, lf, rg; while(cin>>n>>q) { if(!n && !q) return 0; for(int i=1;i<=n;i++) l[i]=i-1, r[i]=i+1; r[n]=0; while(q--) { cin>>lf>>rg; l[r[rg]] = l[lf]; r[l[lf]] = r[rg]; if(l[lf]) cout<<l[lf]<<" "; else cout<<"* "; if(r[rg]) cout<<r[rg]<<"\n"; else cout<<"*\n"; } cout<<"-\n"; } return 0; }

Almost Shortest Path (UVa 12144, UVaLive 4210, Regionals 2008 >> Latin America - South America)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121

/// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 502 struct Z { int v, cost; bool operator < (const Z &p) const { return p.cost<cost; } }; Z z, z2; int shortest[MX], forbidden[MX][MX]; vector<Z> adj[MX]; vector<int> parent[MX]; priority_queue<Z>pq; int dijkstra(int src, int dst, int node) { for(int i=0; i<node; i++) shortest[i]=1e9; z.v = src; z.cost = 0; pq.push(z); shortest[src]=0; while(!pq.empty()) { z = pq.top(); pq.pop(); int l = adj[z.v].size(); for(int i=0; i<l; i++) { z2 = adj[z.v][i]; if(forbidden[z.v][z2.v]==1) continue; if(shortest[z2.v]>shortest[z.v]+z2.cost) { parent[z2.v].clear(); parent[z2.v].push_back(z.v); z2.cost = shortest[z2.v]= shortest[z.v]+z2.cost; pq.push(z2); } else if(shortest[z2.v]==shortest[z.v]+z2.cost) parent[z2.v].push_back(z.v); } } return shortest[dst]; } void removeEdge(int src, int dst) { if(dst==src) return; for(int i=0;i<parent[dst].size();i++) { forbidden[ parent[dst][i] ][dst] = 1; removeEdge(src, parent[dst][i]); } return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc,kk=1, node, edge, u, v, cost, src, dst; while(cin>>node>>edge && node) { cin>>src>>dst; for(int i=0; i<edge; i++) { cin>>u>>v>>cost; z.v = v; z.cost = cost; adj[u].push_back(z); } int tmp = 1e9; int mn = dijkstra(src, dst, node); //initial if(mn<1e9) { removeEdge(src, dst); //remove edges of shortest tmp = dijkstra(src, dst, node); //second time } if(tmp==1e9) tmp = -1; cout<<tmp<<endl; CLR(forbidden); for(int i=0;i<node;i++) { adj[i].clear(); parent[i].clear(); } } return 0; }

Reverse Integer (LeetCode)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: int reverse(int x) { bool flag = false; if(x<0) { flag = true; x*=-1; } int rev = 0; while(x) { if((rev*10)/10 != rev) return 0; // checking overflow rev = rev*10 + x%10; x/=10; } if(flag) rev*=-1; return rev; } };