brain-teaser R problem - programming problem solving in R

Question

I am trying to write a function to solve a novel problem:

Given the following data:

S = c(19, 10, 12, 10, 24, 25, 22)
k = 4 

I am trying to calculate a function. I want to print the maximal subset of S in which any sum of 2 numbers in S' is not evenly divisibly by k

So one answer might be S' = [10, 12, 25] and the other could be S' = [10, 22, 24].

Another example:

if S = {1, 7, 2, 4} and K = 3

Then

1 + 7 = 8
1 + 2 = 3
1 + 4 = 5
7 + 2 = 9
7 + 4 = 11
2 + 4 = 6

That is S' = {1, 7, 4} and will never sum to a multiple of k = 3

Answer 1

There is a linear time algorithm for this. This algorithm is well explained by orezvani in this post on Computer Science section of stackexchange. I translated the orezvani pseudo code in R:

max_subset<-function(S,K){
  R <- S %% K
  Res <- c()
  for(k in 1:(ceiling(K/2)-1)){
    index_k = which(R==k)
    index_K_k = which(R==(K-k))
    if(length(index_k) >= length(index_K_k)){
      Res <- c(Res, S[index_k])
    }else{
      Res <- c(Res, S[index_K_k])
    }
  }
  print(R)
  Res <- c(Res, S[which(R==0)][1])
  if(K %% 2 == 0){
    Res <- c(Res, S[which(R==(K/2))][1])
  }
  return(Res)
}

I tried with different example:

• with S <- c(1, 7, 2, 4) and K = 3 give 1 7 4;
• with S <- c(3, 17, 12, 9, 11, 15) and K = 5 give 11 17 12 15
• with S <- c(3, 7, 2, 9, 1) and K = 3 give 7 1 3
• with S <- c(19, 10, 12, 10, 24, 25, 22) and K = 4 give 25 12 10

In order to be more understandable I tried to be as similar as possible to the pseudocode, probably my solution could be optimized using R language specific features.