24
2
We define a binarray as an array satisfying the following properties:
- it's non-empty
- the first value is a
1
- the last value is a
1
- all other values are either
0
or1
For instance, the array [ 1, 1, 0, 1 ]
is a valid binarray.
The task
Given a non-empty array A of non-negative integers and a positive integer N, your job is to find a binarray B of length N which allows to generate A by summing an unrestricted number of copies of B, shifted by an unrestricted number of positions.
Example
A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
N = 4
For this input, the binarray B = [ 1, 1, 0, 1 ]
would be a valid answer because we can do:
[ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
-----------------------------------------------
= [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Rules
- Input can be taken in any reasonable format.
- Output can be either a native array (e.g.
[1, 1, 0, 1]
) or a binary string with or without a separator (e.g."1,1,0,1"
or"1101"
) - You're only required to print or return one valid binarray. Alternatively, you may choose to print or return all of them when several solutions exist.
- You are not required to support inputs that do not lead to any solution.
- The sum may include implicit zeros which do not overlap with any copy of B. The second zero in the above sum is such an implicit zero.
- Your can assume that the maximum size of A is 100 and the maximum size of B is 30.
- This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.
Test cases
Input : N = 1 / A = [ 1, 2, 3, 4, 5 ]
Output: [ 1 ]
Input : N = 2 / A = [ 1, 2, 100, 99 ]
Output: [ 1, 1 ]
Input : N = 3 / A = [ 1, 1, 1 ]
Output: [ 1, 1, 1 ]
Input : N = 3 / A = [ 1, 1, 3, 2, 2 ]
Output: [ 1, 1, 1 ]
Input : N = 3 / A = [ 1, 0, 2, 1, 1, 1, 0, 0, 1, 0, 1 ]
Output: [ 1, 0, 1 ]
Input : N = 4 / A = [ 1, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1 ]
Input : N = 4 / A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1 ]
Input : N = 4 / A = [ 1, 1, 0, 2, 1, 0, 1 ]
Output: [ 1, 0, 0, 1 ] or [ 1, 1, 0, 1 ]
Input : N = 5 / A = [ 1, 3, 6, 9, 8, 6, 3, 4 ]
Output: [ 1, 1, 1, 0, 1 ]
Input : N = 8 / A = [ 2, 1, 0, 2, 3, 3, 1, 2, 1 ]
Output: [ 1, 0, 0, 1, 1, 1, 0, 1 ]
Input : N = 10 / A = [ 1, 2, 1, 2, 2, 1, 3, 3, 3, 2, 3, 0, 2, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 ]
Input : N = 13 / A = [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 ]
Output: [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]
Input : N = 5 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1, 1 ]
Input : N = 6 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 0, 0, 0, 1 ]
Input : N = 7 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 0, 0, 0, 1, 1 ]
Input : N = 9 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 1, 0, 1, 0, 1, 0, 1 ]
What's the largest value of
N
that should reasonably be supported? – Neil – 2017-03-30T10:50:16.447@Neil I've added size limits on both A and B. – Arnauld – 2017-03-30T11:01:26.953
If you treat the array as each element to the power of two it is find an odd divisor between 2^n-1 and 2^n – fəˈnɛtɪk – 2017-03-30T13:05:01.410
1@fəˈnɛtɪk Maybe, but for
N=4, A = [ 1, 1, 2, 4, 1, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1 ]
, you get 30459 which is divisible by both 11 and 13 yet only one of[ 1, 1, 0, 1 ]
and[ 1, 0, 1, 1 ]
is a valid answer. – Neil – 2017-03-30T15:28:06.4401@fəˈnɛtɪk These numbers aren't written in base 2 so rules of arithmetic don't apply. For instance, you explicitly cannot carry when adding. – BallpointBen – 2017-03-30T22:46:53.127
2Please add these test cases, which seem to break nearly all the posted answers: N = 3, A = [1, 0, 2, 0, 2, 0, 1], output = [1, 0, 1]; N = 3, A = [1, 1, 1, 0, 0, 0, 1, 1, 1], output = [1, 1, 1]. – Anders Kaseorg – 2017-06-02T19:38:29.577