how to solve this without a loop?

Question

we're given 3 numbers y, x, and n. we're asked to find the largest k in case 1 <= k <= n and k % x = y. for example: input: 1 2 100 output: 99

what i can write is like:

#include <stdio.h>
int main()
{
   int y, x, n, max = 1;
   scanf("%d %d %d", &y, &x, &n);
   for (int k = 1; k <= n; k++)
   {
        if ((k % x == y) && (k >= max))
        max = k;
   }
   printf("%d", max);
   return 0;
}

it totally works right. but the problem is the program should be written without using any loop or if. anyone has any idea??

Answer 1

This answer assumes all numbers are non-negative, x is non-zero, and 0 ≤ y < x.

The largest number satisfying the conditions, if it exists, is (n-y)/x*x + y.

Proof:

Let m be the largest multiple of x not greater than n-y. Then n-y = m+r for some 0 ≤ r < x. (If r were negative, m would be greater than n-y. If it were x or greater, m would not be the largest multiple, as m+x would be a multiple of x not greater than n-y.)

Then (n-y)/x = (m+r)/x = m/x since integer division discards the remainder. So (n-y)/x*x = m.

Since m is a multiple of x, m % x = 0. Then (m+y) % x = y, so (n-y)/x*x + y = y.

To see this is the largest such number not greater than n, observe the next larger number with a remainder of y is (n-y)/x*x + y + x = m + y + x = m + y + r + (x-r) = (n-y) + y + (x-r) = n + (x-r), and we know x-r is positive, so this is greater than n.

Note: Regarding the condition 1 ≤ k, this is automatically satisfied if n is large enough to permit such a solution, since the formula produces the largest k ≤ n whose remainder modulo x is y. If the k resulting from the formula does not satisfy 1 ≤ k, no solution exists.

Answer 2

I am going for a full range (+ and -) x, y answer with no int overflow and clearly determine when no solution is possible.

---

Given:

1 <= k <= n
k % x == y

k % x == y implies
k = quotient * x + y where quotient is some integer.

---

When x == 0, then
any_int % 0 is not defined, so in C we cannot certainly form an answer.
1 <= n is also required in all cases.

if (x == 0 || n < 1) No_solution;

---

When x > 0, then
y >= 0 (positive_int % x is never < 0) and
y < x (positive_int % x is always < x).
With k % x == y and 1 <= k <= n, then
n >= y must be true for a solution.

if (x > 0 && (y < 0 || y >= x || y > n)) No_solution;

After rejecting above no solution combinations:

quotient * x + y <= n       // leads to ...
quotient <= (n-y)/x         // quotient is >= 0 and overflow not possible
largest_k = (n-y)/x * x + y // largest_k >= 0 and overflow not possible
if (largest_k == 0) No_solution;

---

When x < 0, then
y >= 0 (positive_int % x is never < 0) and
y < -x (positive_int % x is always < -x).^*1
(Recall a%b is not a mod b when negatives values are involved.

if (x < 0 && (y < 0 || y > -1 - x || y > n)) No_solution;

The rest of the analysis follows the x > 0 case, except quotient <= 0

---

All together

if (x == 0 || n < 1 || y < 0 || y > n) return No_solution;
if (x > 0 && y >= x) return No_solution;
if (x < 0 && y > -1 - x) return No_solution;

int quotient = (n-y)/x;
int largest_k = quotient * x + y;
if (largest_k == 0) return No_solution;
printf("Largest k: %d\n", largest_k);

// I suspect simplifications possible - maybe later.

---

^*1 y < -x could be re-written as y <= -1 - x. This form handles all negative x including INT_MIN.

Answer 3

The given program finds the largest integer k which satisfies the conditions (k % x == y) and (k >= max) for the given values of y, x, and n. This can be done without a loop by using the formula for arithmetic progression.

The largest integer k that satisfies the condition (k % x == y) can be written as k = x * q + y, where q is an integer. So, we need to find the largest q such that x * q + y <= n.

The largest q can be found using the formula q = floor((n - y) / x). Here, floor is the function that rounds down to the nearest integer.

Then, we can compute k as k = x * q + y. If k >= max, then max = k.

Here is the modified code without the loop:

#include <stdio.h>
#include <math.h>

int main()
{
   int y, x, n, max = 1;
   scanf("%d %d %d", &y, &x, &n);
   
   int q = floor((n - y) / (double)x); // compute largest q
   int k = x * q + y; // compute k
   if (k >= max) max = k; // update max if necessary
   
   printf("%d", max);
   return 0;
}

Note that we need to include the math.h header file for the floor function. Also, we need to cast x to a double before dividing to ensure that the result is a floating-point number.