PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Chef bought several sacks of flour.
Each sack has a weight of either 1 or 2 kilograms.
Chef knows he has N kilograms of flour in total.
Is it possible he bought an equal number of sacks that weigh 1 and 2 kilograms?
EXPLANATION:
This problem can be solved by modeling it using simple algebra.
Suppose Chef did buy an equal number of 1 kg and 2 kg bags - say, he bought X bags of each.
Then, the total amount of flour he has must equal X + 2\cdot X = 3\cdot X.
X comes from the 1 kg bags, and 2\cdot X comes from the 2 kg bags.
There are N kilograms in total, so this is only possible if 3\cdot X = N.
This in turn tells us that X = \frac{N}{3}.
Now, clearly X has to be an integer (since it’s the number of bags of each type.)
\frac{N}{3} will be an integer if and only if N is a multiple of 3.
So, the answer is Yes if N is a multiple of 3, and No otherwise.
In most languages, this can be checked using the % operator, where N % 3 denotes the remainder when N is divided by 3 (so we need to check if N % 3 equals 0.)
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n%3 == 0) cout << "Yes\n";
else cout << "No\n";
}