Codeforces Round #629 (Div 3) A problem with optimized approach

2 min readJan 15, 2021

While we write code, we continuously make decisions and choose between solutions that may seem equivalent at first. Later it usually turns out that some choices result in a more efficient program than others, so a quest for best coding practices and optimization techniques naturally arises, and we begin to see the whole development process as an optimization problem to solve. While doing competitive programming, many times we face the problem of TLE (time limit exceeded) in our code. Hence we need to makes our code optimized.

Let's take an example of Codeforces Round #629 (Div 3) A problem.

Problem Statement

A. Divisibility Problem

time limit per test :1 second

memory limit per test:256 megabytes

input

standard input

output

standard output

You are given two positive integers aa and bb. In one move you can increase aby 1 (replace a with a+1). Your task is to find the minimum number of moves you need to do in order to make a divisible by b. It is possible, that you have to make 0 moves, as a is already divisible by b. You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1≤t≤10⁴) — the number of test cases. Then t test cases follow.

The only line of the test case contains two integers a and b (1≤a,b≤10⁹).

Output

For each test case print the answer — the minimum number of moves you need to do in order to make a divisible by b.

Example :

Input :

10 4

13 9

100 13

123 456

92 46

Output :

333

After looking at the question, the first approach that comes to our mind is the brute force approach of using a while loop to check for a%b and increment the count.

The c++ code for this approach is :

#include<iostream>

using namespace std;

int fun(long int a,long int b)

{

long int count=0;

while(a%b!=0)

{

count++;

a++;

}

return count;

}

int main()

{

long int a,b;

int t;

cin>>t;

for(int i=0;i<t;i++)

{

cin>>a>>b;

cout<<fun(a,b)<<endl;

}

return 0;

}

This gets accepted for the small values of a and b. But shows TLE for larger values. So we need an optimized solution for this problem.

#include<iostream>

using namespace std;

int fun(long int a,long int b)

{

long int count=0;

if(a%b==0){return count;}

else

{

int mod=(a%b);

count=b-mod;

}