Question 2 of 9: Programming — Self-Describing Integers

Question 2: Programming — Self-Describing Integers (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A positive integer, entered as a sequence of decimal digits (positions labelled 0 to $n-1$ left to right).

Find. Whether, for every position $p$, the digit stored there equals the count of how many array entries equal $p$.

Approach. Read the number as a string into a digit array (the hint), then for every position count occurrences of that position's own index value across the whole array and compare against the stored digit; any single mismatch rejects the number.

1. State the check as one condition per position. $$\text{self-describing} \iff \forall p\in\{0,\dots,n-1\}:\ \text{digit}[p] = \big|\{\,i : \text{digit}[i]=p\,\}\big|$$ This is a closed condition on the array against itself — no external data is needed, only two nested scans.

   #include <stdio.h>
   #include <string.h>
   
   #define MAXLEN 16
   
   int is_self_describing(int digits[], int len)
   {
       int pos, i, count;
       for (pos = 0; pos < len; pos++) {
           count = 0;
           for (i = 0; i < len; i++)
               if (digits[i] == pos) count++;
           if (count != digits[pos])
               return 0;                 /* fails at this position */
       }
       return 1;
   }
   
   int main(void)
   {
       char buf[MAXLEN + 1];
       int digits[MAXLEN], len, i;
   
       printf("Enter a positive integer: ");
       if (scanf("%16s", buf) != 1) return 1;
   
       len = (int) strlen(buf);
       for (i = 0; i < len; i++)
           digits[i] = buf[i] - '0';
   
       if (is_self_describing(digits, len))
           printf("%s is self-describing.\n", buf);
       else
           printf("%s is NOT self-describing.\n", buf);
       return 0;
   }

2. Trace the paper's own examples. For 2020 (positions 0,1,2,3 hold digits 2,0,2,0): position 0's value 2 must equal the count of 0's among the digits — digits are 2,0,2,0, and there are indeed two 0's; position 1's value 0 must equal the count of 1's — there are none; position 2's value 2 must equal the count of 2's — there are two; position 3's value 0 must equal the count of 3's — there are none. All four positions check out. $$\boxed{\text{is\_self\_describing}(2020) = \text{true}}$$ 1210 and 3211000 verify the same way, and a number such as 1234 fails immediately at position 0: it claims one 0, but 1234 contains none.