Finding denominator which the dividend has the maximum remainder with

Question

I need to find the maximum remainder for n divided by any integer number from 1 to n, and the denominator which this remainder is found with.

In my implementation fun1 works as expected and returns the max remainder, fun2 is supposed to give 3 but its giving 2 .probably mistake is at break statement.

Sample input: 5

Expected output: 2 3.

My output: 2 2.

#include <iostream>
#include <algorithm>

using namespace std;

int fun2(int a);
int fun1(int n ,int num);

int main(){
    int n = 0; int num = 0;;
    cin >> n;
    int p = fun1(n, num);
    cout << p << "\n";
    cout << fun2(p);
}

int fun1(int n, int num){
    int b = 0;
    
    for(int i = 1; i <= n; i++){
        num = n % i;
        b = max(num, b);
    }
    
    return b;
    
}

int fun2(int n,int p ){
     int num = 0; int c = 0; int d = 0;
    for(int i = 1; i <= n; i++){
        num = n % i;
        c = max(num, c);
        
        if(c == p){
            break;
        }
        d = i;
    }
    return d;
}

Answer 1

Since you already managed to successfully find the biggest remainder, you may get use of this function and return the number this remainder is found with:

std::pair<int, int> biggestRemDem(int value) {
    int dm = 1;
    int rm = 0;
    
    for(int i = dm; i <= value; ++i){
        const auto tmpRm = value % i;
        if (tmpRm > rm) {
            rm = tmpRm;
            dm = i;
        }
    }
    
    return { rm, dm };
    
}

The signature of the function needs to return std::pair however, but you no longer need the std::max, so the headers required to include are also changed:

#include <iostream>
#include <utility>

std::pair<int, int> biggestRemDem(int value);

int main(){
    int n{};
    std::cin >> n;
    const auto result = biggestRemDem(n);
    std::cout << result.first << " " << result.second << std::endl;
}

Answer 2

I need to find the maximum remainder for n divided by any integer number from 1 to n, and the denominator which this remainder is found with.

It seems that the asker decided to solve this in two steps. They wrote a function fun1 returning the maximum remainder and a function fun2, which fed with the previously calculated remainder, returns the corresponding dividend.

While not an efficient approach, it could work if implemented correctly, but that's not the case.

Other than some (very) bad naming choices, we can find:

• In the original version of the posted code, fun2 has a function prototype with a single parameter and it is called passing the value returned by fun1, which is the maximum remainder. The problem is that this way the function has no way to know what was the original value of n and actually declares a local n, initialized to zero, so that the body of the loop for(int i = 1; i <= n; i++) is never executed.
  The actual version of this question shows a definition of fun2 with two parameters, that can't compile unless both the prototype and the call site are changed accordingly.

• Assuming that the original n and the remainder p were succesfully passed to fun2, there still would be another issue:

  int fun2(int n, int p ) {
    int c = 0, d = 0;
    for(int i = 1; i <= n; i++) {
      int num = n % i;
      c = max(num, c);
  
      if(c == p){  // So, if we reach the passed remainder...
        break;     // We break out of the loop, skipping...
      }
      d = i;       // this line, meaning...
    }
    return d;      // That the dividend previous to the correct one is returned!
  }
  

  They could just return i; when c == p.

The answer by The Dreams Wind presents a much better approach to this task. I'd like to suggest an O(1) solution, though. Consider these points:

• The result of n % i can't be equal or greater than i. It's in the range [0, i).

• n / 2 is the greatest number that can divide n other than n itself. It means that all the numbers i in (n/2, n) are such that n % i > 0.

• For every number i in (n/2, n), we can actually say that n % i = n - i.

So, when n is greater than 2, the i corresponding to the maximum remainder is just 1 + n/2 and said remainder is n - n/2 - 1.

Answer 3

In fun2 you have:

    if(c == p){
        break;
    }
    d = i;

When you found the right index so that c == p the break will exit the loop and d == i; is not execute. Therefore d has the value from the previous loop, i.e. one less than you need.

---

Apart from that the code really smells:

fun1

• should not have a second argument sum.
• should remember the index where if found the largest remainder and you would be done

fun2

• the maximum remainder is p, no need to max(num, c). Actually drop the c alltogether and just use num == p
• n % 1 == 0 and n % n == 0. The loop will always break with i < n. Might as well not have a conditional: for(int i = 1; ; i++)
• you need d because at the end of the loop i disappears. Why not pull i out of the loop? int i; for(i = 1; ; i++)
• and now you can use a different conditional again

    int fun2(int n,int p ){
        int i;
        for(i = 1; n % i != p; i++) { }
        return i;
    }

or

    int fun2(int n,int p ){
        int i = 1;
        for(; n % i != p; i++) { }
        return i;
    }

or

    int fun2(int n,int p ){
        int i = 1;
        while(n % i != p) ++i;
        return i;
    }