Interview Question
Country: United States
package main
import "fmt"
// _GetAllSums variants of summ
func _GetAllSums(A, N int) []map[int]int {
if N == 0 || A == 0 {
return []map[int]int{{}}
}
if A > N {
return _GetAllSums(N, N)
}
if A == 1 {
return []map[int]int{{1: N}}
}
result := _GetAllSums(A-1, N)
t := N - A
countA := 1
for t >= 0 {
tmp := _GetAllSums(A-1, t)
for _, v := range tmp {
v[A] = countA
result = append(result, v)
}
t -= A
countA++
}
return result
}
func Factorial(N int) int64 {
if N < 0 {
N = -N
}
result := int64(1)
for i := N; i > 1; i-- {
result = result * int64(i)
}
return result
}
func CountSums(A, N int) int64 {
r := _GetAllSums(A, N)
result := int64(0)
// Calculate result with permutations with repeating elements
for _, variant := range r {
length := 0
denominator := int64(1)
for _, nums := range variant {
length += nums
denominator *= Factorial(nums)
}
if length > 0 {
result += Factorial(length) / denominator
}
}
return result
}
func main() {
fmt.Println(CountSums(3, 4)) // Output: 7
}
With python generators
def generate_sequence(n):
i = 0
while i < n:
j = i + 1
while j < n:
yield [(i,j), i+j]
j = j + 1
i = i + 1
def get_sequence_sum(n, a):
return (x[0] for x in generate_sequence(n) if x[1] == a)
print list(get_sequence_sum(10, 7))
print list(get_sequence_sum(12, 10))
print list(get_sequence_sum(8, 9))
With python generators
def generate_sequence(n):
i = 0
while i < n:
j = i + 1
while j < n:
yield [(i,j), i+j]
j = j + 1
i = i + 1
def get_sequence_sum(n, a):
return (x[0] for x in generate_sequence(n) if x[1] == a)
print list(get_sequence_sum(10, 7))
print list(get_sequence_sum(12, 10))
print list(get_sequence_sum(8, 9))
Probably - and it is highly probably - the sequences are simply integers one after another.
- NoOne January 26, 2017So, given start (1) and end(3) the sequences can be :
( You dont have to select all the elements )
1,1,1,1
2,2,
1,1,2,2
1,2,1,2
1,2,2,1
2,1,1,2
1,3
3,1
.... etc.