nondivisiblesubet.go

// Given an array of integer numbers, we need to find
// maximum size of a subset such that sum of each pair
// of this subset is not divisible by K.
// Examples :

// Input :  arr[] = [3, 7, 2, 9, 1]
//          K = 3
// Output : 3
// Maximum size subset whose each pair sum
// is not divisible by K is [3, 7, 1] because,
// 3+7 = 10,
// 3+1 = 4,
// 7+1 = 8        all are not divisible by 3.
// It is not possible to get a subset of size
// bigger than 3 with the above-mentioned property.

// Input : arr[] = [3, 17, 12, 9, 11, 15]
//         K = 5
// Output : 4

// We can solve this problem by computing modulo of array numbers
// with K. if sum of two numbers is divisible by K, then if one of
// them gives remainder i, other will give remainder (K – i).
// First we store frequencies of numbers giving specific
// remainder in a frequency array of size K. Then we loop
// for all remainders i and include max(f[i], f[K – i]).
// Why? a subset with no pair sum divisible by K must include
// either elements with remainder f[i] or with remainder f[K – i].
// Since we want to maximize the size of subset, we pick
// maximum of two sizes.
// In below code array numbers with remainder 0 and remainder
// K/2 are handled separately. If we include more than 2 numbers
// with remainder 0 then their sum will be divisible by K, so we
// have taken at max 1 number in our consideration, same is the
// case with array numbers giving remainder K/2.

//Sourced answer from https://www.geeksforgeeks.org/subset-no-pair-sum-divisible-k/?ref=rp


package main

import (
	"fmt"
	"math"
)

func main() {
	xi1 := []int32{3, 7, 2, 9, 1}
	k1 := int32(3)
	res1 := nonDivisibleSubset(xi1, k1)
	fmt.Println(res1, "should be 3")

	xi2 := []int32{19, 10, 12, 24, 22, 25, 22}
	k2 := int32(4)
	res2 := nonDivisibleSubset(xi2, k2)
	fmt.Println(res2, "should be 3")

	xi3 := []int32{1, 7, 2, 4}
	k3 := int32(3)
	res3 := nonDivisibleSubset(xi3, k3)
	fmt.Println(res3, "should be 3")

}

func nonDivisibleSubset(xi []int32, k int32) int32 {
	// Array for storing frequency of modulo values
	xr := make([]int32, k)
	n := int32(len(xi))

	// Fill frequency array with values modulo k
	for i := int32(0); i < n; i++ {
		xr[xi[i]%k]++ 
	}

	// If k is even, then update xr[k/2]
	if k%2 == 0 {
		fl64 := math.Min(float64(xr[k/2]), 1)
		fl64toi32 := int32(fl64)
		xr[k/2] = fl64toi32
	}

	// Initialize results by minimum of 1 or
	// count of numbers giving remainder 0
	resfl64 := math.Min(float64(xr[0]), 1)

	// Choose the maximum count of numbers giving remainder i or k-1
	for i := int32(1); i <= k/2; i++ {
		resfl64 += math.Max(float64(xr[i]), float64(xr[k-i]))

	}
	return int32(resfl64)
}