Question

1 : An array a is defined to be self-referential if for i=0 to a.length-1, a[i] is the count of the number of times that the value i appears in the array. As the following table indicates, {1, 2, 1, 0} is a self-referential array.

Here are some examples of arrays that are not self-referential:

{2, 0, 0} is not a self-referential array. There are two 0s and no 1s. But unfortunately there is a 2 which contradicts a[2] = 0.

{0} is not a self-referential array because there is one 0, but since a[0] = 0, there has to be no 0s.

{1} is not a self-referential array because there is not a 0 in the array as required by a[0] = 1.

Self-referential arrays are rare. Here are the self-referential arrays for arrays of lengths up to 10 elements:

{1, 2, 1, 0} (see above)
{2, 0, 2, 0} (there are two 0s, no 1s, two 2s and no 3s
{2, 1, 2, 0, 0}  (there are two 0s, one 1, two 2s, no 3s and no 4s)
{3, 2, 1, 1, 0, 0, 0} (there are three 0s, two 1s, one 2, one 3, no 4s, 5s or 6s)
{4, 2, 1, 0, 1, 0, 0, 0} (there are four 0s, two 1s, one 2, no 3s, one 4, and no 5s, 6s, or 7s)
{5, 2, 1, 0, 0, 1, 0, 0, 0} (there are five 0s, two 1s, one 2, no 3s or 4s, one 5, and no 6s, 7s, or 8s)
{6, 2, 1, 0, 0, 0, 1, 0, 0, 0} (there are six 0s, two 1s, one 2, no 3s, 4s, or 5s, one 6, and no 7s, 8s, or 9s)

Write a function named isSelfReferential that returns 1 if its array argument is self-referential, otherwise it returns 0.

If you are programming in Java or C#, the function signature is
   int isSelfReferential(int[ ] a)

If you are programming in C or C++, the function signature is
   int isSelfReferential(int a[ ], int len) where len is the number of elements in the array

Answer 1

We have to just verify the condition whether a[i] is the count that element i appears in the array for that we can keep a count array for 0 to n-1 and then verify whether it matches the count or not in the original array.

The code is

#include <iostream>

using namespace std;
int isSelfReferential(int a[],int len){
int counts[len]={};//counts array to store the counts of integers
for(int i=0;i<len;i++){
if(a[i]<len){
//if a[i] is in range of 0 to n-1 then increment the count
counts[a[i]]++;
}
}
//verifying the result now
for(int i=0;i<len;i++)
{
if(a[i]!=counts[i])
return 0;//if count of i is not a[i]
}
return 1;
}
int main() {
//testing
int a[]={1, 2, 1, 0};
int b[]={5, 2, 1, 0, 0, 1, 0, 0, 0};
int c[]={5, 2, 1, 0, 0, 1, 3, 2, 0};
int d[]={1,2, 2, 1, 0, 0, 1, 0, 0, 0};
cout<<isSelfReferential(a,sizeof(a)/sizeof(int))<<"\n";
cout<<isSelfReferential(b,sizeof(b)/sizeof(int))<<"\n";
cout<<isSelfReferential(c,sizeof(c)/sizeof(int))<<"\n";
cout<<isSelfReferential(d,sizeof(d)/sizeof(int))<<"\n";
}