14
For another challenge I am writing, I need to verify that test cases are solveable with bounded integers. Specifically, I need to verify the following, for a non-empty array of integers A
and an integer bit width n
:
- All integers
a
inA
satisfy-2**(n-1) <= a < 2**(n-1)
(representable withn
-bit two's complement integers). - The length of
A
is less than2**n
. - The sum of
A
satisfies-2**(n-1) <= sum(A) < 2**(n-1)
. - All combinations of elements in
A
satisfy all of the above conditions.
Naturally, I've decided to outsource this problem to you!
Given an array of integers A
and a positive integer bit width n
, verify that A
satisfies the conditions above.
Test Cases
[0, 0, 0], 2: True
[0, 0, 0, 0], 2: False (violates #2)
[1, 2, 3, 4, 5], 8: True
[1, 2, 3, 4, 5], 2: False (violates all conditions)
[1, 2, 3, 4, 5], 5: True
[-3, 4, 1], 4: True
[10, 0, -10], 4: False (violates #1 and #4)
[27, -59, 20, 6, 10, 53, -21, 16], 8: False (violates #4)
[-34, 56, 41, -4, -14, -54, 30, 38], 16: True
[-38, -1, -11, 127, -35, -47, 28, 89, -8, -12, 77, 55, 75, 75, -80, -22], 7: False (violates #4)
[-123, -85, 6, 121, -5, 12, 52, 31, 64, 0, 6, 101, 128, -72, -123, 12], 12: True
Reference Implementation (Python 3)
#!/usr/bin/env python3
from itertools import combinations
from ast import literal_eval
def check_sum(L, n):
return -2**(n-1) <= sum(L) < 2**(n-1)
def check_len(L, n):
return len(L) < 2**n
def check_elems(L, n):
return all(-2**(n-1) <= a < 2**(n-1) for a in L)
A = literal_eval(input())
n = int(input())
OUTPUT_STR = "{}, {}: {}".format(A, n, "{}")
if not (check_elems(A, n) and check_len(A, n) and check_sum(A, n)):
print(OUTPUT_STR.format(False))
exit()
for k in range(1, len(A)):
for b in combinations(A, k):
if not check_sum(b, n):
print(OUTPUT_STR.format(False))
exit()
print(OUTPUT_STR.format(True))
Sandbox – Mego – 2017-12-13T04:02:03.023
Must we handle the empty list? – Mr. Xcoder – 2017-12-14T05:18:32.283
@Mr.Xcoder No, I'll clarify. – Mego – 2017-12-14T05:19:31.697