C++ Divide or Subtract

[muutwikaeliaserndafetango]

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

#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;
}

 

[simong1993]

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:

#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.

 

[BlackCube]

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.

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