cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2021 · MediumBig integer arithmetic

Exact Power-of-Two Expression

National Olympiad — Regional round (2021 season)

Submission name: expr.cpp

Solve in Editor →

Problem summary

Compute the exact integer 2^n−m, where m may be negative and may have thousands of digits.

Input

The exponent n and signed decimal integer m.

Output

The exact decimal value of 2^n−m.

Constraints

1 ≤ n ≤ 10000; −2^n ≤ m ≤ 2^n.

Worked example

Input and output for the worked example discussed below.

Input

6 3

Output

61

Solution analysis

  1. Ordinary integer types cannot hold 2^10000. Represent nonnegative integers as decimal strings. Begin with power="1" and double it n times, carrying from the least significant digit toward the front.
  2. If m is negative, the expression becomes 2^n+|m|, so use grade-school addition. Otherwise subtract m from the power using a borrow. The source guarantees m≤2^n, so this subtraction is never negative.
  3. For n=6, doubling produces 1,2,4,8,16,32,64. Subtracting 3 gives 61. For n=3 and m=−7, add 7 to 8 instead, giving 15. Remove redundant leading zeros but keep one zero for a zero result.

Why it works

Each string operation implements the positional base-ten carry or borrow rule, preserving the exact represented integer. Induction over the n doublings gives 2^n. The final sign-dependent addition or subtraction is algebraically identical to 2^n−m.

Complexity: O(n²) digit operations and O(n) space: 2^n has Θ(n) decimal digits, and n doublings each scan at most that many digits. Final addition/subtraction is O(n).

Watch out. Do not parse m with stoll or use floating-point pow. Handle a leading minus sign, borrow chains, and the exact zero case.

Commented C++17 solution

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
string add(string a,string b){
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    string result;
    int carry=0;
    for(size_t i=0;i<max(a.size(),b.size())||carry;i++){
        int sum=carry;
        if(i<a.size()){
            sum+=a[i]-'0';
        }
        if(i<b.size()){
            sum+=b[i]-'0';
        }
        result.push_back(char('0'+sum%10));
        carry=sum/10;
    }
    reverse(result.begin(),result.end());
    return result;
}
string subtract(string a,string b){
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    int borrow=0;
    for(size_t i=0;i<a.size();i++){
        int digit=a[i]-'0'-borrow;
        if(i<b.size()){
            digit-=b[i]-'0';
        }
        borrow=digit<0;
        if(borrow){
            digit+=10;
        }
        a[i]=char('0'+digit);
    }
    while(a.size()>1&&a.back()=='0'){
        a.pop_back();
    }
    reverse(a.begin(),a.end());
    return a;
}
int main(){
    int exponent;
    string m;
    cin>>exponent>>m;
    string power="1";
    for(int i=0;i<exponent;i++){
        // Doubling the exact string avoids floating-point rounding.
        power=add(power,power);
    }
    if(m[0]=='-'){
        cout<<add(power,m.substr(1))<<'\n';
    }
    else{
        cout<<subtract(power,m)<<'\n';
    }
}

Source: Arena Olimpiici ↗