working on this problem looking for some input

[markyrocks]

 given a number of elements in an array $n, a divisor $k and an array $s[$n] find sets of numbers in $s[] that NO 2 numbers added together are cleanly divisible by $k.  

the problem  asks for the number of numbers inside of the set with the greatest amount of numbers inside of it<~~update.

Mod($s[$x]+$s[y],$k) <> 0    ;would produce 2 numbers not eliminated.  I've been beating on this thing for hours, have gotten pretty close.   i have to call it a night probably take one of you all 10 min to crack.   

in this method i have what will return a good result if all of the numbers are greater than k.... if any of them are less it gets messed up and also if $k is even i end up with an odd final array size

and the idea is 0 is eliminated so its gone and working from the outside edges in i.e ($k=4, whatever is greater between 1 & 3 gets added to the tally... anyway i was working on it in c++ decided to try to solve in auto it (maybe my luck would be better. lol

!! also the idea is to do this is the most efficient way possible sure brute forcing it is an option but the idea is to come up with an algorithm type solution.  Thanks for any help in advance.

;~ $n=15
;~ $k=7
;~ $str="278 576 496 727 410 124 338 149 209 702 282 718 771 575 436"        ; correct = 11

;~ $n=4
;~ $k=3
;~ $str="1 7 2 4"      ;correct answer is 3

$n=10
$k=4
$str="1 2 3 4 5 6 7 8 9 10"              ;correct = 5

dim $a[$k]
$highest=0
$s=StringSplit($str," ",2)

if $k==0 or $k==1 then ConsoleWrite(1)

for $x=0 to UBound($s)-1

    if $s[$x]>$k then  $a[Mod($s[$x],$k)]+=1
    next

for $x=1 to Floor($k/2)

$highest+= $a[$x] > $a[UBound($a)-(1+$x)] ? $a[$x] : $a[UBound($a)-(1+$x)]

next

;~ for $x=1 to UBound($a)-1

;~  ConsoleWrite($a[$x] & @CRLF)

;~ Next

ConsoleWrite($highest)

 

this is a c++ solution i was working on i figured out i need to add another iteration to it or do something this solution basically involves having 2 arrays and comparing them to each other.  Idk how much sense this idea makes i was pretty tired when i started playing around with the concept.  As it stands its nowhere near efficient so i'd have to seriously cut some fat to get it to work.

Spoiler

int nonDivisibleSubset(int k, vector<int> s) {
int highest=0;
vector<int> kk(s.size(),0);
vector<int> s2=s;
                       //0|1|2|3
                       //1|2|3|0  <~~comparison concept...

for(int y=0;y<s.size();y++){
    for(int x=s.size()-(1+y);x>-1;x--){
        if(s[x]+s2[x]>k && (s[x]+s2[x])%k!=0){kk[x]++;}
    }  // this needs a 3rd iteration....
    s2.erase(s2.begin());
}

for(int x=0;x<kk.size();x++){
    cout<<kk[x]<<'\n';
}
//total hasn't even been considered....
return highest;
}

 

 

Edited September 3, 2020 by markyrocks

[jchd]

49 minutes ago, markyrocks said:

given a number of elements in an array $n, a divisor $k and an array $s[$n] find sets of numbers in $s[] that NO 2 numbers added together are cleanly divisible by $k.

Sorry but you seem to solve another problem and return the highest element of something, not a list of subsets of $s satisfying the above condition.

If I had to solve the posed problem, I'd build a 2D array $a[$n][2] for storing $s[$i] and Mod[$s[$i], $k] for $i in [0..$n-1]. This way you use Mod() less times. Sorting $a over column 1 will help. Building a list of wanted subsets of $s boils to eliminate partitions of $k (with any combination of elements = zero), that is subsets having Mod(sum($a[$i][1]), $k) = 0.

I strongly suspect there is no fast algorithm to produce a correct result for that problem, something common in many problems of additive number theory.

OTOH if you're only interested in the cardinal of the above result, you still have to enumerate the possible partitions, making the process no faster.

[markyrocks]

14 hours ago, jchd said:

Sorry but you seem to solve another problem and return the highest element of something, not a list of subsets of $s satisfying the above condition.

If I had to solve the posed problem, I'd build a 2D array ...

What you're proposing is the brute force method i described earlier.   I think i figured out what I need to do.

If $s{1,2,3,4} and $k=3 $s[x]%$k the remainders would be 2,1,0,1 then 2+1=$k so a number with a remainder of 2 will only be able to pair up with numbers that the remainder is 0 or 2. So subset 1 would be =2

So if a number whose remainder is 1 can pair with numbers whose remainder is 1 or 0 so subset 2 would be =3.  If a remainder is 0 it will only be able to pair with 0 or 1 so subset 3 would be 3 aswell highest subset =3.  

I just needed to sleep on it.  But as you can see this is a problem that could be looped through thousands of times maybe millions if dim $s[10^9].  So the way I'm solving it drastically reduces the number of times the original array needs looped through. Then you need to loop thought an array that contains the remainders and count them then compare the counted remainders.   Ill finish it up here in a bit and post the final solution. 

 

Edit: on second thought the remainder 0 needs eliminated or some kinda special consideration bc theres no opposite

 

Edited September 2, 2020 by markyrocks

[markyrocks]

I figured i'd post the solution (that seems to work for the test cases that are included).  So as you see it only actually loops through the original array 1 time and does the division and counting of the remainders at the same time.

then it loops through the array that contains the remainders and compares the current count to its opposite provided $x is greater than 0 and not equal to clean division of $k/2.  The point of this is bc if $k is even and $x=$k/2 then those numbers can't be included bc they eliminate themselves.  Idk now else to explain it. anyways here it is. 

Spoiler

expandcollapse popup

;~ ; Script Start - Add your code below here
$n=15
$k=7
$str="278 576 496 727 410 124 338 149 209 702 282 718 771 575 436"        ; correct = 11

;~ $n=4
;~ $k=3
;~ $str="1 7 2 4"      ;correct answer is 3

;~ $n=10
;~ $k=4
;~ $str="1 2 3 4 5 6 7 8 9 10"              ;correct = 5

dim $a[$k]
$highest=0
$s=StringSplit($str," ",2)

if $k==0 or $k==1 then
    ConsoleWrite(1)
    Exit
    EndIf


for $x=0 to UBound($s)-1
$a[Mod($s[$x],$k)]+=1
next

for $x=1 to Floor($k/2)

if $x<>$k/2 then
$highest += $a[$x]>$a[UBound($a)-$x] ? $a[$x] : $a[UBound($a)-$x]
EndIf
next

$highest+=($a[0]>0) + (Mod($k,2)=0 and ($a[$k/2]>0))

 ConsoleWrite($highest)

 

 

Edited September 3, 2020 by markyrocks

[jchd]

3 hours ago, markyrocks said:

If $s{1,2,3,4} and $k=3 $s[x]%$k the remainders would be 2,1,0,1

Modulus would rather be 1, 2, 0, 1 respectively. Sets of modulus which can't sum up 2 by 2 to 0. That is {1, 0, 1}, corresponding to numbers {1, 3, 4} and {2, 0} corresponding to numbers {2, 3}.

So all the subsets with at least two numbers which satisfy the condition are:
{1, 3} : 1+3 ≡ 1 mod 3
{1, 4} : 1+4 ≡ 2 mod 3
{3, 4} : 3+4 ≡ 1 mod 3
{1, 3, 4} : all 3 combinations above
{2, 3} : 2+3 ≡ 2 mod 3

I still fail to understand how you can find a scalar result, while the problem ask for sets.

Edited September 3, 2020 by jchd

[markyrocks]

30 minutes ago, jchd said:

 

I still fail to understand how you can find a scalar result, while the problem ask for sets.

the problem  asks for the number of numbers inside of the set with the greatest amount of numbers inside of it. sorry it looks like i failed to explain that detail in the original post.  i'll update it.  I was pretty tired when i posted this.

Edited September 3, 2020 by markyrocks

[jchd]

So you ask for the max cardinal of the subsets I listed in the post above? Then yes the answer is 3 for this input.

I'm curious: can you explicitly list the set of 5 numbers corresponding to the case in your code sample:
 

$n=10
$k=4
$str="1 2 3 4 5 6 7 8 9 10"              ;correct = 5

I can't find the same result, I find 4.

Edited September 3, 2020 by jchd

[markyrocks]

1 hour ago, jchd said:

So you ask for the max cardinal of the subsets I listed in the post above? Then yes the answer is 3 for this input.

I'm curious: can you explicitly list the set of 5 numbers corresponding to the case in your code sample:
 

$n=10
$k=4
$str="1 2 3 4 5 6 7 8 9 10"              ;correct = 5

I can't find the same result, I find 4.

I updated the above code it should be correct now apparently you need to add 1 to the final answer if more than one number has the remainder of 0 and also add one if $k/2 results in a whole number and $a[$k/2]>0

 

the numbers in the set you're asking for are....1,4,5,6,9 or 1,4,5,9,10  i think...

the answer in c++, just tested it and its correct for all cases (more than 20)

 

Spoiler

int nonDivisibleSubset(int k, vector<int> s) {
int highest=0;
vector<int> r(k,0);
if(k==0 || k==1){return 1;}
for(int x=0;x<s.size();x++){
    r[s[x]%k]++;
}

for(int x=1;(x*2)<k;x++){

        highest+= r[x]>r[r.size()-x] ? r[x] : r[r.size()-x];
}

 highest += (r[0] > 0) + (k%2 == 0 && r[k/2] > 0);
return highest;
}

 

 

 

Edited September 3, 2020 by markyrocks

[jchd]

Oops, you're right. I was considering sums of more than 2 modulii. It was late (3h30 AM).