# Welcome!

By registering with us, you'll be able to discuss, share and private message with other members of our community.

# C++Divide or Subtract

#### muutwikaeliaserndafetango

##### New Coder
Hi everyone. I’ve been trying to solve this competitive programming problem but I can’t. Can anyone please help?

Problem Statement:

B. Divide or Subtract?

time limit per test

1 second

memory limit per test

1024 megabytes
You are given two integers: n and k. Your goal is to make the number n equal to 0.
To achieve this you can perform two types of operations: subtract k from n or divide n by k and round down to the nearest integer. In other words, you can either assign n←n−k or assign n←⌊nk⌋.
What is the minimum number of operations required to make n equal to zero?
Input
Each test contains multiple test cases. The first line of input contains a single integer t — the number of test cases in this test (1≤t≤104).
In the i-th of the following lines two integers n and k for the i-th test case are given (0≤n≤109; 1≤k≤109).
Output
For each test case, output a single integer on a separate line — the minimum number of operations required to make the corresponding n equal to zero.
Example
input

Copy​
5
12 1
10 2
137 2
137 12
1024 2
output

Copy
12
3
7
2
10

Code:
``````#include <iostream>
using namespace std;

int min_operations(int n, int k) {
int operations = 0;
while (n > 0) {
if (k == 1) {
return n; // Only subtraction is possible.
}
if (n < k) {
operations += n; // Need to subtract k until n becomes 0.
break;
}
int remainder = n % k;
if (remainder != 0) {
n -= remainder;
operations += remainder;
} else {
n /= k;
operations++;
}
}
return operations;
}

int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
cout << min_operations(n, k) << endl;
}
return 0;
}``````

Last edited by a moderator:
Hey! I see where you're going with this, and your code looks mostly solid. I think you’re close, but I noticed a couple of things that could improve the solution:

1. Subtraction Optimization: When `k == 1`, you’re correctly handling it by just returning `n` because you can only subtract. This part is good.

2. Handling Cases Where `n < k`: In cases where `n < k`, you’re directly subtracting until `n` reaches 0, which is also fine.

3. Optimization on Division: You’re already doing `n -= remainder` when `n % k != 0`, which is good for aligning `n` with a divisible number. But remember, after subtracting, you should increment the operations by `1` (for the subtraction) plus the division steps.

4. Rechecking Division After Subtraction: After subtracting the remainder, check again if `n` is divisible by `k` to ensure you’re not missing additional division steps.

Here’s an optimized version of your code with slight improvements:

Code:
``````#include <iostream>
using namespace std;

int min_operations(int n, int k) {
int operations = 0;

while (n > 0) {
if (k == 1) {
return n; // Only subtraction is possible, just subtract `n` times.
}
if (n < k) {
operations += n; // If `n` is smaller than `k`, just subtract it until zero.
break;
}

int remainder = n % k; // Calculate remainder.

if (remainder != 0) {
n -= remainder; // Subtract remainder to make `n` divisible by `k`.
operations += remainder; // Increment operations by the number of subtractions.
} else {
n /= k; // Divide `n` by `k`.
operations++; // Count this division as one operation.
}
}
return operations;
}

int main() {
int t;
cin >> t;

while (t--) {
int n, k;
cin >> n >> k;
cout << min_operations(n, k) << endl;
}
return 0;
}``````

Explanation:
• When `n` is divisible by `k`, you divide it and count that as one operation.
• When `n` is not divisible by `k`, you subtract the remainder (to make it divisible by `k`), count the subtractions, and continue dividing.
• The edge case where `k == 1` is handled separately because you can only subtract in that case.

I hope this helps! Let me know if you need further clarification.

if n<k then the number of operations is 1

floor(n/k)=0

Forget the program and reread the question.

I could be wrong.
Code:
``````pseudocode:

function operations(n,k)
if n == 0 then
op = 0
elseif k == 1 then
op = n  ;subtractions
elseif n < k then
op = 1  ;divide
elseif n == k then
op = 1  ;subtract
else
op = 1 + operations(floor(n/k),k)
endif
return op``````

Last edited: