vishwas gupta
Reputation: 75
Finding total number of arrays
I have an array A consisting of N integers. I also have an integer K. I want to find out number of different arrays I can obtain from array A by applying the following operation exactly K times.
- Pick some element in the array and multiply it by -1
array A=[2,3,2] and k=2 I have four possible arrays
1.[2,3,2]
2.[-2,-3,2]
3.[-2,3,-2]
4.[2,-3,-2]
This can be calculated as sum of ∑nCr where r is {k,k-2,k-4....}.
Edit
But for combination of positive and negative numbers lets say our array is A=[-1,2,3] and k=3,all possible combinations are
1.[1,2,3] 2.[-1,-2,3] 3.[-1,2,-3] 4.[1,-2,-3]
which are in total 4 arrays, which are in total 4 arrays also.
I just submitted the code which I think should be right is
int main()
{
int n,k;
int arr[11];
arr[0]=1;
for (int i=1;i<=10;i++)
{
arr[i]=arr[i-1]*i;
//cout<<arr[i]<<" ";
}
long int ans=0;
cin>>n>>k; / n for number of elements and k for operations
for (int i=0;i<n;i++)
{
int num; array element
cin>>num;
}
int i=(k%2==0?2:1);
for(;i<=k;i+=2)
{
ans=ans+arr[n]/(arr[k]*arr[n-k]);
}
if(k%2==0)
ans=arr[n]/(arr[k]*arr[n-k])+1;
if(n==1 && k%2==1)
ans=1;
cout<<ans;
}
But it is giving wrong answer. Please help me regarding this.
Upvotes: 4
Views: 430
Answers (2)
warrior
Reputation: 29
I didn't have much reputation to comment so i'm asking here.
@Stormwind This won't be the case because array may contain 0 also.
Upvotes: 1
Stormwind
Reputation: 824
This caters for a huge multidimensional setup. Some brute-force coding, using the parallel array processing language Dyalog APL reveals the following number of unique results, for K = 1...10 and N = 1...14:
┌────┬───┬───┬───┬───┬───┬───┬───┬───┬───┬────┬────┬────┬────┬────┐
│ │N=1│N=2│N=3│N=4│N=5│N=6│N=7│N=8│N=9│N=10│N=11│N=12│N=13│N=14│
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=1 │1 │2 │3 │4 │5 │6 │7 │8 │9 │10 │11 │12 │13 │14 │
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=2 │1 │2 │4 │7 │11 │16 │22 │29 │37 │46 │56 │67 │79 │92 │
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=3 │1 │2 │4 │8 │15 │26 │42 │64 │93 │130 │176 │232 │299 │378 │
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=4 │1 │2 │4 │8 │16 │31 │57 │99 │163│256 │386 │562 │794 │1093│
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=5 │1 │2 │4 │8 │16 │32 │63 │120│219│382 │638 │1024│1586│2380│
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=6 │1 │2 │4 │8 │16 │32 │64 │127│247│466 │848 │1486│2510│4096│
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=7 │1 │2 │4 │8 │16 │32 │64 │128│255│502 │968 │1816│3302│5812│
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=8 │1 │2 │4 │8 │16 │32 │64 │128│256│511 │1013│1981│3797│7099│
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=9 │1 │2 │4 │8 │16 │32 │64 │128│256│512 │1023│2036│4017│7814│
├────┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┤
│K=10│1 │2 │4 │8 │16 │32 │64 │128│256│512 │1024│2047│4083│8100│
└────┴───┴───┴───┴───┴───┴───┴───┴───┴───┴────┴────┴────┴────┴────┘
One cannot see any distinct pattern in there, although it indeed does exist. One thing we can see is that when performing the negation enough times (ie. K is "exhausts" the array), we seem to reach 2^(N-1) unique results (ie. 1, 2, 4, 8, 16 etc).
Assume we do it brute-forcedly. If we have a 4-length array (ie. N=4) and K=1, elements 1, 2, 3 or 4 of the array can be negated:
┌─┬─┬─┬─┐
│1│2│3│4│
└─┴─┴─┴─┘
If K=2, we get a new a dimension (now a 2-dimensional problem) and now have 16 possible index pairs for negation:
┌───┬───┬───┬───┐
│1 1│1 2│1 3│1 4│
├───┼───┼───┼───┤
│2 1│2 2│2 3│2 4│
├───┼───┼───┼───┤
│3 1│3 2│3 3│3 4│
├───┼───┼───┼───┤
│4 1│4 2│4 3│4 4│
└───┴───┴───┴───┘
For example the [4 2] means that array[4] and array[2] would both be multiplied by -1.
Setting K=3 makes it 3-dimensional:
┌─────┬─────┬─────┬─────┐┌─────┬─────┬─────┬─────┐┌─────┬─────┬─────┬─────┐┌─────┬─────┬─────┬─────┐
│1 1 1│1 1 2│1 1 3│1 1 4││2 1 1│2 1 2│2 1 3│2 1 4││3 1 1│3 1 2│3 1 3│3 1 4││4 1 1│4 1 2│4 1 3│4 1 4│
├─────┼─────┼─────┼─────┤├─────┼─────┼─────┼─────┤├─────┼─────┼─────┼─────┤├─────┼─────┼─────┼─────┤
│1 2 1│1 2 2│1 2 3│1 2 4││2 2 1│2 2 2│2 2 3│2 2 4││3 2 1│3 2 2│3 2 3│3 2 4││4 2 1│4 2 2│4 2 3│4 2 4│
├─────┼─────┼─────┼─────┤├─────┼─────┼─────┼─────┤├─────┼─────┼─────┼─────┤├─────┼─────┼─────┼─────┤
│1 3 1│1 3 2│1 3 3│1 3 4││2 3 1│2 3 2│2 3 3│2 3 4││3 3 1│3 3 2│3 3 3│3 3 4││4 3 1│4 3 2│4 3 3│4 3 4│
├─────┼─────┼─────┼─────┤├─────┼─────┼─────┼─────┤├─────┼─────┼─────┼─────┤├─────┼─────┼─────┼─────┤
│1 4 1│1 4 2│1 4 3│1 4 4││2 4 1│2 4 2│2 4 3│2 4 4││3 4 1│3 4 2│3 4 3│3 4 4││4 4 1│4 4 2│4 4 3│4 4 4│
└─────┴─────┴─────┴─────┘└─────┴─────┴─────┴─────┘└─────┴─────┴─────┴─────┘└─────┴─────┴─────┴─────┘
...where for example [1 1 1] means that array[1] would be multiplied by -1 three times in a row. Now we can also see that some of the 64 possibilities are duplicates.
When doing the brute-force calculation, there was actually 10-dimensional data involved. Eventually the system run out of memory, as the data grew enourmous.
It doesn't matter what numeric values the array contains. Instead, we of course only need to figure out the sign changes, ie. multiplications with -1. Here are the possible number of unique combinations for K = 1...5 and N = 1...5:
┌───┬────┬───────────┬───────────────────────────────┬─────────────────────────────────────────────────────────────────────────────────┬─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ │N=1 │N=2 │N=3 │N=4 │N=5 │
├───┼────┼───────────┼───────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│K=1│┌──┐│┌────┬────┐│┌──────┬──────┬──────┐ │┌────────┬────────┬────────┬────────┐ │┌──────────┬──────────┬──────────┬──────────┬──────────┐ │
│ ││-1│││-1 1│1 -1│││-1 1 1│1 -1 1│1 1 -1│ ││-1 1 1 1│1 -1 1 1│1 1 -1 1│1 1 1 -1│ ││-1 1 1 1 1│1 -1 1 1 1│1 1 -1 1 1│1 1 1 -1 1│1 1 1 1 -1│ │
│ │└──┘│└────┴────┘│└──────┴──────┴──────┘ │└────────┴────────┴────────┴────────┘ │└──────────┴──────────┴──────────┴──────────┴──────────┘ │
├───┼────┼───────────┼───────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│K=2│┌─┐ │┌───┬─────┐│┌─────┬───────┬───────┬───────┐│┌───────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐ │┌─────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┐ │
│ ││1│ ││1 1│-1 -1│││1 1 1│-1 -1 1│-1 1 -1│1 -1 -1│││1 1 1 1│-1 -1 1 1│-1 1 -1 1│-1 1 1 -1│1 -1 -1 1│1 -1 1 -1│1 1 -1 -1│ ││1 1 1 1 1│-1 -1 1 1 1│-1 1 -1 1 1│-1 1 1 -1 1│-1 1 1 1 -1│1 -1 -1 1 1│1 -1 1 -1 1│1 -1 1 1 -1│1 1 -1 -1 1│1 1 -1 1 -1│1 1 1 -1 -1│ │
│ │└─┘ │└───┴─────┘│└─────┴───────┴───────┴───────┘│└───────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘ │└─────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┘ │
├───┼────┼───────────┼───────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│K=3│┌──┐│┌────┬────┐│┌──────┬──────┬──────┬────────┐│┌────────┬────────┬────────┬────────┬──────────┬──────────┬──────────┬──────────┐│┌──────────┬──────────┬──────────┬──────────┬──────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┐ │
│ ││-1│││-1 1│1 -1│││-1 1 1│1 -1 1│1 1 -1│-1 -1 -1│││-1 1 1 1│1 -1 1 1│1 1 -1 1│1 1 1 -1│-1 -1 -1 1│-1 -1 1 -1│-1 1 -1 -1│1 -1 -1 -1│││-1 1 1 1 1│1 -1 1 1 1│1 1 -1 1 1│1 1 1 -1 1│1 1 1 1 -1│-1 -1 -1 1 1│-1 -1 1 -1 1│-1 -1 1 1 -1│-1 1 -1 -1 1│-1 1 -1 1 -1│-1 1 1 -1 -1│1 -1 -1 -1 1│1 -1 -1 1 -1│1 -1 1 -1 -1│1 1 -1 -1 -1│ │
│ │└──┘│└────┴────┘│└──────┴──────┴──────┴────────┘│└────────┴────────┴────────┴────────┴──────────┴──────────┴──────────┴──────────┘│└──────────┴──────────┴──────────┴──────────┴──────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┘ │
├───┼────┼───────────┼───────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│K=4│┌─┐ │┌───┬─────┐│┌─────┬───────┬───────┬───────┐│┌───────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬───────────┐│┌─────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┐│
│ ││1│ ││1 1│-1 -1│││1 1 1│-1 -1 1│-1 1 -1│1 -1 -1│││1 1 1 1│-1 -1 1 1│-1 1 -1 1│-1 1 1 -1│1 -1 -1 1│1 -1 1 -1│1 1 -1 -1│-1 -1 -1 -1│││1 1 1 1 1│-1 -1 1 1 1│-1 1 -1 1 1│-1 1 1 -1 1│-1 1 1 1 -1│1 -1 -1 1 1│1 -1 1 -1 1│1 -1 1 1 -1│1 1 -1 -1 1│1 1 -1 1 -1│1 1 1 -1 -1│-1 -1 -1 -1 1│-1 -1 -1 1 -1│-1 -1 1 -1 -1│-1 1 -1 -1 -1│1 -1 -1 -1 -1││
│ │└─┘ │└───┴─────┘│└─────┴───────┴───────┴───────┘│└───────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴───────────┘│└─────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┘│
├───┼────┼───────────┼───────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│K=5│┌──┐│┌────┬────┐│┌──────┬──────┬──────┬────────┐│┌────────┬────────┬────────┬────────┬──────────┬──────────┬──────────┬──────────┐│┌──────────┬──────────┬──────────┬──────────┬──────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬──────────────┐│
│ ││-1│││-1 1│1 -1│││-1 1 1│1 -1 1│1 1 -1│-1 -1 -1│││-1 1 1 1│1 -1 1 1│1 1 -1 1│1 1 1 -1│-1 -1 -1 1│-1 -1 1 -1│-1 1 -1 -1│1 -1 -1 -1│││-1 1 1 1 1│1 -1 1 1 1│1 1 -1 1 1│1 1 1 -1 1│1 1 1 1 -1│-1 -1 -1 1 1│-1 -1 1 -1 1│-1 -1 1 1 -1│-1 1 -1 -1 1│-1 1 -1 1 -1│-1 1 1 -1 -1│1 -1 -1 -1 1│1 -1 -1 1 -1│1 -1 1 -1 -1│1 1 -1 -1 -1│-1 -1 -1 -1 -1││
│ │└──┘│└────┴────┘│└──────┴──────┴──────┴────────┘│└────────┴────────┴────────┴────────┴──────────┴──────────┴──────────┴──────────┘│└──────────┴──────────┴──────────┴──────────┴──────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴──────────────┘│
└───┴────┴───────────┴───────────────────────────────┴─────────────────────────────────────────────────────────────────────────────────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
This definitely shows us the pattern. If K is odd, we get odd number of negations, and if K is even, we get even number of negations. Both can happen up to the amount allowed by the arrays size N. Ie. if K=5, we can get 1 or 3 or 5 negations OR what fits into the array; ie. if N=4, we cannot ofc have 5 negations, but only 1 or 3.
Hence, we can solve this using factorial/binomial (m!n) which tells us the possible number of unique combinations of m elements in n numeric space. Ie. 3!5 would return 10, as there are 10 ways to combine 3 elements of 1,2,3,4,5:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
4!5 would return 5:
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
and 3!3 would return 1:
1 2 3
The formula for this problem is (2 examples):
combinations = (1!6) + (3!6) + (5!6) + (7!6) // K=7, N=6 - note that K is odd
combinations = (0!6) + (2!6) + (4!6) + (6!6) // K=6, N=6 - note that K is even
Note:
0!n is always 1
n!n is always 1
(>n)!n is always 0 (for example 12!7 would return 0)
To solve this task, execute (again, for a large set, where K = 1...10 and N = 1...14):
┌────┬────────────────────────────────────┬────────────────────────────────────┬────────────────────────────────────┬────────────────────────────────────┬────────────────────────────────────┬────────────────────────────────────┬────────────────────────────────────┬────────────────────────────────────┬────────────────────────────────────┬──────────────────────────────────────────┬──────────────────────────────────────────┬──────────────────────────────────────────┬──────────────────────────────────────────┬──────────────────────────────────────────┐
│ │N=1 │N=2 │N=3 │N=4 │N=5 │N=6 │N=7 │N=8 │N=9 │N=10 │N=11 │N=12 │N=13 │N=14 │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=1 │(1!1) │(1!2) │(1!3) │(1!4) │(1!5) │(1!6) │(1!7) │(1!8) │(1!9) │(1!10) │(1!11) │(1!12) │(1!13) │(1!14) │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=2 │(0!1)+(2!1) │(0!2)+(2!2) │(0!3)+(2!3) │(0!4)+(2!4) │(0!5)+(2!5) │(0!6)+(2!6) │(0!7)+(2!7) │(0!8)+(2!8) │(0!9)+(2!9) │(0!10)+(2!10) │(0!11)+(2!11) │(0!12)+(2!12) │(0!13)+(2!13) │(0!14)+(2!14) │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=3 │(1!1)+(3!1) │(1!2)+(3!2) │(1!3)+(3!3) │(1!4)+(3!4) │(1!5)+(3!5) │(1!6)+(3!6) │(1!7)+(3!7) │(1!8)+(3!8) │(1!9)+(3!9) │(1!10)+(3!10) │(1!11)+(3!11) │(1!12)+(3!12) │(1!13)+(3!13) │(1!14)+(3!14) │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=4 │(0!1)+(2!1)+(4!1) │(0!2)+(2!2)+(4!2) │(0!3)+(2!3)+(4!3) │(0!4)+(2!4)+(4!4) │(0!5)+(2!5)+(4!5) │(0!6)+(2!6)+(4!6) │(0!7)+(2!7)+(4!7) │(0!8)+(2!8)+(4!8) │(0!9)+(2!9)+(4!9) │(0!10)+(2!10)+(4!10) │(0!11)+(2!11)+(4!11) │(0!12)+(2!12)+(4!12) │(0!13)+(2!13)+(4!13) │(0!14)+(2!14)+(4!14) │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=5 │(1!1)+(3!1)+(5!1) │(1!2)+(3!2)+(5!2) │(1!3)+(3!3)+(5!3) │(1!4)+(3!4)+(5!4) │(1!5)+(3!5)+(5!5) │(1!6)+(3!6)+(5!6) │(1!7)+(3!7)+(5!7) │(1!8)+(3!8)+(5!8) │(1!9)+(3!9)+(5!9) │(1!10)+(3!10)+(5!10) │(1!11)+(3!11)+(5!11) │(1!12)+(3!12)+(5!12) │(1!13)+(3!13)+(5!13) │(1!14)+(3!14)+(5!14) │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=6 │(0!1)+(2!1)+(4!1)+(6!1) │(0!2)+(2!2)+(4!2)+(6!2) │(0!3)+(2!3)+(4!3)+(6!3) │(0!4)+(2!4)+(4!4)+(6!4) │(0!5)+(2!5)+(4!5)+(6!5) │(0!6)+(2!6)+(4!6)+(6!6) │(0!7)+(2!7)+(4!7)+(6!7) │(0!8)+(2!8)+(4!8)+(6!8) │(0!9)+(2!9)+(4!9)+(6!9) │(0!10)+(2!10)+(4!10)+(6!10) │(0!11)+(2!11)+(4!11)+(6!11) │(0!12)+(2!12)+(4!12)+(6!12) │(0!13)+(2!13)+(4!13)+(6!13) │(0!14)+(2!14)+(4!14)+(6!14) │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=7 │(1!1)+(3!1)+(5!1)+(7!1) │(1!2)+(3!2)+(5!2)+(7!2) │(1!3)+(3!3)+(5!3)+(7!3) │(1!4)+(3!4)+(5!4)+(7!4) │(1!5)+(3!5)+(5!5)+(7!5) │(1!6)+(3!6)+(5!6)+(7!6) │(1!7)+(3!7)+(5!7)+(7!7) │(1!8)+(3!8)+(5!8)+(7!8) │(1!9)+(3!9)+(5!9)+(7!9) │(1!10)+(3!10)+(5!10)+(7!10) │(1!11)+(3!11)+(5!11)+(7!11) │(1!12)+(3!12)+(5!12)+(7!12) │(1!13)+(3!13)+(5!13)+(7!13) │(1!14)+(3!14)+(5!14)+(7!14) │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=8 │(0!1)+(2!1)+(4!1)+(6!1)+(8!1) │(0!2)+(2!2)+(4!2)+(6!2)+(8!2) │(0!3)+(2!3)+(4!3)+(6!3)+(8!3) │(0!4)+(2!4)+(4!4)+(6!4)+(8!4) │(0!5)+(2!5)+(4!5)+(6!5)+(8!5) │(0!6)+(2!6)+(4!6)+(6!6)+(8!6) │(0!7)+(2!7)+(4!7)+(6!7)+(8!7) │(0!8)+(2!8)+(4!8)+(6!8)+(8!8) │(0!9)+(2!9)+(4!9)+(6!9)+(8!9) │(0!10)+(2!10)+(4!10)+(6!10)+(8!10) │(0!11)+(2!11)+(4!11)+(6!11)+(8!11) │(0!12)+(2!12)+(4!12)+(6!12)+(8!12) │(0!13)+(2!13)+(4!13)+(6!13)+(8!13) │(0!14)+(2!14)+(4!14)+(6!14)+(8!14) │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=9 │(1!1)+(3!1)+(5!1)+(7!1)+(9!1) │(1!2)+(3!2)+(5!2)+(7!2)+(9!2) │(1!3)+(3!3)+(5!3)+(7!3)+(9!3) │(1!4)+(3!4)+(5!4)+(7!4)+(9!4) │(1!5)+(3!5)+(5!5)+(7!5)+(9!5) │(1!6)+(3!6)+(5!6)+(7!6)+(9!6) │(1!7)+(3!7)+(5!7)+(7!7)+(9!7) │(1!8)+(3!8)+(5!8)+(7!8)+(9!8) │(1!9)+(3!9)+(5!9)+(7!9)+(9!9) │(1!10)+(3!10)+(5!10)+(7!10)+(9!10) │(1!11)+(3!11)+(5!11)+(7!11)+(9!11) │(1!12)+(3!12)+(5!12)+(7!12)+(9!12) │(1!13)+(3!13)+(5!13)+(7!13)+(9!13) │(1!14)+(3!14)+(5!14)+(7!14)+(9!14) │
├────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┼──────────────────────────────────────────┤
│K=10│(0!1)+(2!1)+(4!1)+(6!1)+(8!1)+(10!1)│(0!2)+(2!2)+(4!2)+(6!2)+(8!2)+(10!2)│(0!3)+(2!3)+(4!3)+(6!3)+(8!3)+(10!3)│(0!4)+(2!4)+(4!4)+(6!4)+(8!4)+(10!4)│(0!5)+(2!5)+(4!5)+(6!5)+(8!5)+(10!5)│(0!6)+(2!6)+(4!6)+(6!6)+(8!6)+(10!6)│(0!7)+(2!7)+(4!7)+(6!7)+(8!7)+(10!7)│(0!8)+(2!8)+(4!8)+(6!8)+(8!8)+(10!8)│(0!9)+(2!9)+(4!9)+(6!9)+(8!9)+(10!9)│(0!10)+(2!10)+(4!10)+(6!10)+(8!10)+(10!10)│(0!11)+(2!11)+(4!11)+(6!11)+(8!11)+(10!11)│(0!12)+(2!12)+(4!12)+(6!12)+(8!12)+(10!12)│(0!13)+(2!13)+(4!13)+(6!13)+(8!13)+(10!13)│(0!14)+(2!14)+(4!14)+(6!14)+(8!14)+(10!14)│
└────┴────────────────────────────────────┴────────────────────────────────────┴────────────────────────────────────┴────────────────────────────────────┴────────────────────────────────────┴────────────────────────────────────┴────────────────────────────────────┴────────────────────────────────────┴────────────────────────────────────┴──────────────────────────────────────────┴──────────────────────────────────────────┴──────────────────────────────────────────┴──────────────────────────────────────────┴──────────────────────────────────────────┘
and the result is identical to the the brute-forced one earlier:
N=1 N=2 N=3 N=4 N=5 N=6 N=7 N=8 N=9 N=10 N=11 N=12 N=13 N=14
K=1 1 2 3 4 5 6 7 8 9 10 11 12 13 14
K=2 1 2 4 7 11 16 22 29 37 46 56 67 79 92
K=3 1 2 4 8 15 26 42 64 93 130 176 232 299 378
K=4 1 2 4 8 16 31 57 99 163 256 386 562 794 1093
K=5 1 2 4 8 16 32 63 120 219 382 638 1024 1586 2380
K=6 1 2 4 8 16 32 64 127 247 466 848 1486 2510 4096
K=7 1 2 4 8 16 32 64 128 255 502 968 1816 3302 5812
K=8 1 2 4 8 16 32 64 128 256 511 1013 1981 3797 7099
K=9 1 2 4 8 16 32 64 128 256 512 1023 2036 4017 7814
K=10 1 2 4 8 16 32 64 128 256 512 1024 2047 4083 8100
These are the total number of unique arrays, after doing the modification K times. Hope this clarifies :-).
Upvotes: 4
Related Questions
- Merge/flatten an array of arrays
- How can I access and process nested objects, arrays, or JSON?
- How to merge two arrays in JavaScript and de-duplicate items
- How to compare arrays in JavaScript?
- Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
- How can I concatenate two arrays in Java?
- How to get the difference between two arrays in JavaScript?
- How to get first N number of elements from an array
- With arrays, why is it the case that a[5] == 5[a]?
- What is the count of subarrays that will include a particular index 'i'?