#include<bits/stdc++.h>
using namespace std;

int main() {
  int a = 1000'000'000,b = 1000'000'000;
  long long product = a * b;
  cout << product << '\n';
  return 0;
}

Overflow!

Even if you declared the product variable as long long, what's happening, in reality, is, first the compiler is multiplying a with b and then it is assigning the output to the product variable and as a and b both are int, that's why the output is also int, but $$$10^{18}$$$ is too much to contain for an int variable.

So how to solve this?

#include<bits/stdc++.h>
using namespace std;

int main() {
  int a = 1000'000'000,b = 1000'000'000;
  long long product = (long long) a * b;
  cout << product << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int get_size(vector<int> a) {
  return (int)a.size();
}
int main() {
  int n = 1000000;
  vector<int> a(n, 0);
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += get_size(a);
  }
  cout << sum << '\n';
  return 0;
}

Nope! The complexity is actually $$$O(n^2)$$$.

This is because you are passing the vector by value — meaning every time you are calling the function the whole vector of $$$10^6$$$ elements is getting passed in the function. So how to solve this?

#include<bits/stdc++.h>
using namespace std;

int get_size(vector<int> &a) {
  return (int)a.size();
}
int main() {
  int n = 1000000;
  vector<int> a(n, 0);
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += get_size(a);
  }
  cout << sum << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 100000;
int main() {
  int test_cases = 100000;
  while (test_cases--) {
    int n; cin >> n;
    vector<int> a(N, 0);
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
    }
    cout << sum << '\n';
  }
  // it is guaranteed that total sum of n is <= 100000
  return 0;
}

It's not $$$100000$$$. It's actually around $$$10^{10}$$$ as every time you are declaring a vector of size $$$10^5$$$. I used to do this mistake a lot in the beginning. How to solve this?

#include<bits/stdc++.h>
using namespace std;

const int N = 100000;
int main() {
  int test_cases = 100000;
  while (test_cases--) {
    int n; cin >> n;
    vector<int> a(n, 0);
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
    }
    cout << sum << '\n';
  }
  // it is guaranteed that total sum of n is <= 100000
  return 0;
}

Also, check this out.

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 5;
  int a[n];
  memset(a, 1, sizeof a);
  for (int i = 0; i < n; i++) {
    cout << a[i] << ' ';
  }
  cout << '\n';
  return 0;
}

memset function is actually for char or 1 byte data types! Check out this to learn more.

Then you might ask I have seen people doing memset(a, -1, sizeof a) or memset(a, 0, sizeof a). Well, that's because it works for $$$0$$$ and $$$-1$$$ accidentally! Check out this comment to learn why memset works for $$$0$$$ and $$$-1$$$ correctly.

Using memset to set all elements in an array to $$$-1$$$ or $$$0$$$ is cool as it works really faster than just looping through all the indices and setting them to $$$-1$$$ or $$$0$$$. But be careful while using it for other numbers.

smash me

Don't use pow() unless you are bound to use this because sometimes the answer won't be exactly what you are expecting, and there will be slight precision errors. For example, it's clear that log2(1 << 30) is $$$30$$$. But sometimes it may consider it as $$$29.9999999999999$$$ and when converting it to int, it will return 29.

Similar to this, as pow() takes double as arguments, pow(5, 2) should return $$$5^2=25.00$$$, but sometimes it may consider it as $$$24.9999999999999$$$ and when converting it to int, it will return $$$24$$$. You may use round(pow(5, 2)) in this particular case to avoid the precision issue or just brute force.

#include<bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v;
  cout << v.size() - 1 << '\n';;
  return 0;
}

Check this out. Or in short, v.size() acts more like unsigned data types.

#include<bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v;
  cout << (int)v.size() - 1 << '\n';;
  return 0;
}

That's why the following code will run indefinitely.

#include<bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v;
  for (int i = 0; i < v.size() - 1; i++) { // use i < (int)v.size() - 1 here
    // do something
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i <= 3; i++) {
    cout << i << '\n';
    printf("%d\n", i + 10);
  }
  return 0;
}

1
11
2
12
3
13

1
2
3
11
12
13

That's because the synchronization has been turned off using the line ios_base::sync_with_stdio(0). Check this out to know more.

So do not mix C-style and C++-style printers after using ios_base::sync_with_stdio(0).

#include<bits/stdc++.h>
using namespace std;

int main() {
  int a = 1, b = 3;
  // we want to take b & 3 and add it to a
  int result = a + b & 3;
  cout << result << '\n';
  return 0;
}

The precedence of the + operator is higher than the & operator, so the operator + operates first, meaning a+b = 4 executes and then the & operator comes into play, so 4&3 executes and the output is clearly 0 for this.

Check out this to learn more about C++ operator precedence.

So how to solve this issue?

#include<bits/stdc++.h>
using namespace std;

int main() {
  int a = 1, b = 3;
  // we want to take b & 3 and add it to a
  int result = a + (b & 3);
  cout << result << '\n';
  return 0;
}

Another similar classic error is 1 << n - 1 is not $$$2^{n}-1$$$, it's actually $$$2^{n-1}$$$ as - has more precedence than the << operator.

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e6;
int main() {
  int minimum = INF;
  for (int i = 1; i <= 10; i++) {
    int x; cin >> x; // the value of x can be up to 10000
    minimum = min(minimum, x * x);
  }
  cout << minimum << '\n';
  return 0;
}

Beginners sometimes don't care about the INF value. For example, here the value of x can be up to $$$10000$$$, meaning the value of x*x, will be up to $$$10^8$$$. But here the value of the minimum variable has been set to $$$10^6$$$, which is not large enough.

So always make sure that the initialized value of a variable is large enough (or small enough).

#include<bits/stdc++.h>
using namespace std;

unordered_map<int, int> mp;
int main() {
  int n = 300000;
  for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    mp[x]++;
  }
  int max_occurrence = 0;
  for (auto [val, cnt]: mp) {
    max_occurrence = max(max_occurrence, cnt);
  }
  cout << max_occurrence << '\n';
  return 0;
}

Because of unordered map! The worst-case time complexity of our code is $$$O(n^2)$$$, that's because unordered map is a hash map and it might take more than $$$O(1)$$$ operations to insert or access in case of the input is not random.

Check this post: Blowing up unordered_map, and how to stop getting hacked on it

So always use a custom hash if you don't want to get blown up.

#include<bits/stdc++.h>
using namespace std;

int main() {
  multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
  // now erase one occurrence of 2
  se.erase(2);
  // now print the elements
  for (auto val: se) {
    cout << val << ' ';
  }
  cout << '\n';
  return 0;
}

That's because if you use a value in the erase() function in a multiset, then all elements will be erased, but if you erase an iterator, then only the element in that iterator will get erased. Check this out for more.

#include<bits/stdc++.h>
using namespace std;

int main() {
  multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
  // now erase one occurrence of 2
  se.erase(se.find(2));
  // now print the elements
  for (auto val: se) {
    cout << val << ' ';
  }
  cout << '\n';
  // 1 1 2 2 3 4 5 5 
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  map<int, int> mp;
  // add 1 to 5 to the map
  for (int i = 1; i <= 5; i++) {
    mp[i]++;
  }
  int cnt = 0;
  // check how many numbers from 1 to 10 exist in the map
  for (int i = 1; i <= 10; i++) {
    if (mp[i]) {
      ++cnt;
    }
  }
  // now print the size of the map
  cout << (int)mp.size() << '\n';
  return 0;
}

No! It's actually $$$10$$$.

That's because of the statement if (mp[i]), mp[i] also inserts the element i into the map even if it doesn't exist. This type of error might get you some unexpected MLEs.

But how to solve this?

#include<bits/stdc++.h>
using namespace std;

int main() {
  map<int, int> mp;
  // add 1 to 5 to the map
  for (int i = 1; i <= 5; i++) {
    mp[i]++;
  }
  int cnt = 0;
  // check how many numbers from 1 to 10 exist in the map
  for (int i = 1; i <= 10; i++) {
    if (mp.find(i) != mp.end()) {
      ++cnt;
    }
  }
  // now print the size of the map
  cout << (int)mp.size() << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 100000;
  set<int> se;
  for (int i = 1; i <= n; i++) {
    se.insert(i);
  }
  // compute the sum of 1 to n
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    // get the iterator containing the smallest element >= i 
    // it will point to i here
    auto it = lower_bound(se.begin(), se.end(), i);
    sum += *it; // *it = i
  }
  cout << sum << '\n';
  return 0;
}

Wrong!

It's actually $$$O(n^2)$$$. Wait, but doesn't lower_bound work in $$$O(\log{n})$$$?

Actually lower_bound(set.begin(), set.end(), value) is not $$$O(\log{n})$$$! Check out this to learn more.

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 100000;
  set<int> se;
  for (int i = 1; i <= n; i++) {
    se.insert(i);
  }
  // compute the sum of 1 to n
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    // get the iterator containing the smallest element >= i 
    // it will point to i here
    auto it = se.lower_bound(i);
    sum += *it; // *it = i
  }
  cout << sum << '\n';
  return 0;
}

Same for upper_bound.

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 1000000;
  string s = "";
  for (int i = 0; i < n; i++) {
    s = s + 'a'; // append a to the string
  }
  cout << s << '\n';
  return 0;
}

It's not $$$O(n)$$$! It's $$$O(n^2)$$$ actually.

Because every time you are using s = s + 'a', on the right side it is accessing the whole string s (which can be $$$O(n)$$$ in size). How to fix this?

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 1000000;
  string s = "";
  for (int i = 0; i < n; i++) {
    s += 'a'; // append a to the string
  }
  cout << s << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  int test_cases; cin >> test_cases;
  // take an array of length n as input
  // print YES if the length is 1 or NO otherwise!
  while (test_cases--) {
    int n; cin >> n; // length of the array
    if (n == 1) {
      cout << "YES\n";
      continue;
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) { // taking the array elements as input
      cin >> a[i];
    }
    cout << "NO\n";
  }
  return 0;
}

When n == 1, you are continuing even before taking the array as input. So the code will give WA in some cases.

2
1
1
2
1 3

It happened to me multiple times before! So please take the whole input first if you want to continue by checking some base cases.

#include<bits/stdc++.h>
using namespace std;

int main() {
  int test_cases; cin >> test_cases;
  // take an array of length n as input
  // print YES if the length is 1 or NO otherwise!
  while (test_cases--) {
    int n; cin >> n; // length of the array
    vector<int> a(n);
    for (int i = 0; i < n; i++) { // taking the array elements as input
      cin >> a[i];
    }
    if (n == 1) {
      cout << "YES\n";
      continue;
    }
    cout << "NO\n";
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int MAX_ELEMENT = 1e5;
int cnt[MAX_ELEMENT + 1];
int main() {
  int test_cases; cin >> test_cases;
  while (test_cases--) {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
      int x; cin >> x;
      cnt[x]++;
    }
    int unique_elements = 0;
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      if (cnt[i] > 0) {
        unique_elements++;
      }
    }
    cout << unique_elements << '\n';
  }
  return 0;
}

Notice that the problem has multiple test cases. But you are not resetting the cnt array in each test! So the counts of previous test cases will still be in the cnt array and will produce WA.

2
1
1
1
2

So always clear everything from the previous tests.

#include<bits/stdc++.h>
using namespace std;

const int MAX_ELEMENT = 1e5;
int cnt[MAX_ELEMENT + 1];
int main() {
  int test_cases; cin >> test_cases;
  while (test_cases--) {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
      int x; cin >> x;
      cnt[x]++;
    }
    int unique_elements = 0;
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      if (cnt[i] > 0) {
        unique_elements++;
      }
    }
    cout << unique_elements << '\n';

    // resetting everything
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      cnt[i] = 0;
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int main() {
  int a = 1e9, b = 1e9, c = 1e9;
  int sum = (a + b + c) % mod;
  cout << sum << '\n';
  int product = a * b % mod;
  cout << product << '\n';
  int random = 1LL * a * (b * c % mod) % mod;
  cout << random << '\n';
  a = 1e8;
  int sub = (a - b) % mod; 
  cout << sub << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int main() {
  // 0 <= a, b, c < mod
  int a = 1e9, b = 1e9, c = 1e9;

  int sum = (a + b + c) % mod; 
  // overflow as (a + b + c) > INT_MAX(=2147483647)
  // better way: ((a + b) % mod + c) % mod
  cout << sum << '\n';

  int product = a * b % mod;
  // overflow as a * b > INT_MAX
  // better way: 1LL * a * b % mod
  cout << product << '\n';

  int random = 1LL * a * (b * c % mod) % mod; 
  // overflow in the (b * c % mod) part
  // correct way: 1LL * a * (1LL * b * c % mod) % mod
  // better way: 1LL * a * b % mod * c % mod
  cout << random << '\n';

  a = 1e8;
  int sub = (a - b) % mod; 
  // not overflow, but when a < b, it will produce a negative number
  // better way: (a - b + mod) % mod
  cout << sub << '\n';

  // Also always make sure that after each arithmetic operation
  // All of your variables are in the range [0, mod-1]
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  long long val= 1e12;
  vector<long long> v({val, val, val});
  // now take sum of all elements
  long long sum = accumulate(v.begin(), v.end(), 0);
  cout << sum << '\n';
  return 0;
}

That's because the initialized variable (0) is an int, so the sum also returns as int. Check this out for more.

#include<bits/stdc++.h>
using namespace std;

int main() {
  long long val= 1e12;
  vector<long long> v({val, val, val});
  // now take sum of all elements
  long long sum = accumulate(v.begin(), v.end(), 0LL); // typecast
  cout << sum << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  vector<double> v({1.23, 2.05, 3.003});
  // now take sum of all elements
  double sum = accumulate(v.begin(), v.end(), 0); // correct way: 0.0
  cout << sum << '\n'; // it outputs 6 which is not intended
  return 0;
}

long long x = (long long)1e18 - 1;
long long k = sqrtl(x);
while (k * k < x) ++k;
while (k * k > x) --k;
cout << k << '\n';

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n = 100000;
  multiset<int> se;
  // insert n instances of 1
  for (int i = 1; i <= n; i++) {
    se.insert(1);
  }
  long long tot = 0;
  // let's count how many 1s are there in the multiset, n times
  for (int i = 1; i <= n; i++) {
    tot += se.count(1);
  }
  cout << tot << '\n';
  return 0;
}

It's not $$$O(n \, \log{n})$$$, it's actually $$$O(n^2)$$$!

Why? Because the time complexity is logarithmic in the size of the container + linear in the number of occurrences of the element and here, the occurrence of $$$1$$$ is $$$n$$$. So use the count() function for multisets carefully!

Also, if you want to check if a number exists in a multiset use the find() function instead of counting the occurrences.