# Largest Remainder

Largest Possible Remainder problem in racket:

```;;lr = largest remainder so far lrd = divisor with largest remainder
(define (largest-remainder n d (lr 0) (lrd 0))
(cond
[(= d 0) (values lr lrd)] ;;catch cases like n = 6, d = 3
[(> lr d) (values lr lrd)] ;;stop when d is < largest remainder
[(> (modulo n d) lr)
(largest-remainder n (sub1 d) (modulo n d) d)] ;;save new largest remainder
[else
(largest-remainder n (sub1 d) lr lrd)])) ;;iterate with d-1
```

Common Lisp translation:

```(defun largest-remainder (n d &optional (lr 0) (lrd 0))
(cond
((<= d 0) (values lr lrd))
((< d lr) (values lr lrd))
(t (let ((r (rem n d)))
(if (> r lr)
(largest-remainder n (1- d) r d)
(largest-remainder n (1- d) lr lrd))))))
```

Iterative in python.

```
def largest_remainder(n,d):
lr = 0
lrd = 0
while (d >= lr) and (d > 0):
if (n % d > lr):
lr = n % d
lrd = d
d -= 1
return (lr,lrd)

print largest_remainder(20,10)
print largest_remainder(6,3)
```

# Limited Median Problem

Another Programming Praxis problem. The problem is nicely constrained by limiting it to 8-bit numbers.

```#lang racket

(define (limited-median xs)
(define xsv (make-vector 256 0))
(for ([x xs])
(vector-set! xsv x (+ 1 (vector-ref xsv x))))
(define half-limit (/ (length xs) 2))
(define (median low high low-count high-count)
(cond
[(< low-count half-limit)
(median (add1 low) high (+ low-count (vector-ref xsv low)) high-count)]
[(< high-count half-limit)
(median low (sub1 high) low-count (+ high-count (vector-ref xsv high)))]
[else
(/ (+ low high) 2)]))
(median 0 255 0 0))

```

Edit: C++

```#include <iostream>
#include <array>
#include <vector>
//#include <cstdio>
//#include <cmath>
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */

//linux: clang++ -std=c++11 -g -Wall limited_median.cpp -o limited_median

float limited_median (std::vector<int> numbers){
std::array<int,256> counting_array;
counting_array.fill(0);
int count = numbers.size();
for (int const& i : numbers) { counting_array[i]++; }
int right = 255;
int right_count = 0;
int left = 0;
int left_count = 0;
int half_limit = count / 2;
while (left_count < half_limit)
{
left_count += counting_array[left];
left ++;
}
while (right_count < half_limit)
{
right_count += counting_array[right];
right --;
}
return (left + right)/ 2.0;

}

int main(int argc, char* argv[]){
std::vector<int> test1 {2,4,5,7,3,6,1};
std::vector<int> test2 {5,2,1,6,3,4};

std::cout << limited_median(test1) << "\n";
std::cout << limited_median(test2) << "\n";

//test with 5000 random numbers
srand(time(NULL));
std::vector<int> test3;
for (int i = 0; i < 5000; i++)
{
test3.push_back((rand() % 256));
}
std::cout << limited_median(test3) << "\n";
return 0;
}
```