cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2009 · MediumModular Arithmetic

Binary Calculator

National Olympiad — Municipal round

Submission name: calc.cpp

Solve in Editor →

Problem summary

Given a binary integer, determine whether it is divisible by seven. If not, find the smallest nonnegative integer to add to obtain a multiple of seven.

Input

One binary integer.

Output

YES if divisible by seven; otherwise the required addition in decimal.

Constraints

At most 1000 binary digits.

Worked example

An independently prepared example for this explanation.

Input

10000

Output

5

Solution analysis

  1. Read the digits without converting the whole integer.
  2. Maintain remainder r; a new bit b changes it to (2r+b) modulo 7.
  3. A nonzero remainder needs an addition of 7−r.

Why it works

The remainder update follows positional notation. The next multiple is exactly 7−r larger when r is nonzero.

Complexity: O(L) time; O(1) auxiliary space.

Watch out. A 1000-bit value does not fit in a built-in integer.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: The remainder update follows positional notation. The next multiple is exactly 7−r larger
// when r is nonzero.
#include<iostream>
#include<iterator>
using namespace std;
int main(){
    char c;
    int r=0;
    while(cin>>c){
        r=(2*r+c-'0')%7;
    }
    if(r==0){
        cout<<"YES\n";
    }
    else{
        cout<<7-r<<'\n';
    }
}

Source: Arena Olimpiici ↗