The way to understand what a snippet of code is doing is to A) understand what it does at a macro-level, which you have done and B) go through each line and understand what it does, then C) work your way backward and forward from what you know, gaining progress a bit at a time. Let me show you what I mean using your example.
Let's start by seeing, broadly (top-down) what the code is doing:
void main(){
// Set up some initial state
int S;
cin >> S;
int ans = 1e9;
// Create a mask, that's neat, we'll look at this later.
for (int mask = 0; mask < 1 << 9; mask++) {
// Loop state
int sum = 0;
string num;
// This loop seems to come up with candidate sums, somehow.
for (int i = 0; i < 9; i++)
if (mask >> i & 1) {
sum += i + 1;
num += char('0' + (i + 1));
}
// Stop if the sum we've found isn't the target
if (sum != S)
continue;
// Keep track of the smallest value we've seen so far
ans = min(ans, stoi(num));
}
// Print out the smallest value
cout << ans << '\n';
}
So, going from what we knew about the function at a macro level, we've found that there are really only two spots that are obscure, the two loops. (If anything outside of those are confusing to you, please clarify.)
So now let's try going bottom-up, line-by-line those loops.
// The number 9 appears often, it's probably meant to represent the digits 1-9
// The syntax 1 << 9 means 1 bitshifted 9 times.
// Each bitshift is a multiplication by 2.
// So this is equal to 1 * (2^9) or 512.
// Mask will be 9 bits long, and each combination of bits will be covered.
for (int mask = 0; mask < 1 << 9; mask++) {
// Here's that number 9 again.
// This time, we're looping from 0 to 8.
for (int i = 0; i < 9; i++) {
// The syntax mask >> i shifts mask down by i bits.
// This is like dividing mask by 2^i.
// The syntax & 1 means get just the lowest bit.
// Together, this returns true if mask's ith bit is 1, false if it's 0.
if (mask >> i & 1) {
// sum is the value of summing the digits together
// So the mask seems to be telling us which digits to use.
sum += i + 1;
// num is the string representation of the number whose sum we're finding.
// '0'+(i+1) is a way to convert numbers 1-9 into characters '1'-'9'.
num += char('0' + (i + 1));
}
}
}
Now we know what the code is doing, but it's hard to figure out. Now we have to meet in the middle - combine our overall understanding of what the code does with the low-level understanding of the specific lines of code.
We know that this code gives up after 9 digits. Why? Because there are only 9 unique non-zero values (1,2,3,4,5,6,7,8,9). The problem said they have to be unique.
Where's zero? Zero doesn't contribute. A number like 209 will always be smaller than its counterpart without the zero, 92 or 29. So we just don't even look at zero.
We also know that this code doesn't care about order. If digit 2 is in the number, it's always before digit 5. In other words, the code doesn't ever look at the number 52, only 25. Why? Because the smallest anagram number (numbers with the same digits in a different order) will always start with the smallest digit, then the second smallest, etc.
So, putting this all together:
void main(){
// Read in the target sum S
int S;
cin >> S;
// Set ans to be a value that's higher than anything possible
// Because the largest number with unique digits is 987654321.
int ans = 1e9;
// Go through each combination of digits, from 1 to 9.
for (int mask = 0; mask < 1 << 9; mask++) {
int sum = 0;
string num;
for (int i = 0; i < 9; i++)
// If this combination includes the digit i+1,
// Then add it to the sum, and append to the string representation.
if (mask >> i & 1) {
sum += i + 1;
num += char('0' + (i + 1));
}
// If this combination does not yield the right sum, try the next combination.
if (sum != S)
continue;
// If this combination does yield the right sum,
// see if it's smaller than our previous smallest.
ans = min(ans, stoi(num));
}
// Print the smallest combination we found.
cout << ans << '\n';
}
I hope this helps!
