Week 5: Notes

jagged arrays

A jagged array is an array of arrays. This is not the same thing as a multidimensional array. A multidimensional array has a rectangular shape, whereas each array in a jagged array can have a different length.

You can allocate a jagged array like this:

    int[][] i = new int[3][];
    i[0] = new int[2];
    i[1] = new int[4];
    i[2] = new int[5];

Now you can get or set elements like this:

i[0][0] = 2;
i[0][1] = 3;
i[1][0] = i[0][0] + 1;

If you like, you can initialize a jagged array as you allocate it:

    int[][] i = {
      new int[] { 2, 3},
      new int[] { 3, 4, 5},
      new int[] { 1, 3, 5, 7, 9}
    };

large integers

We can represent large integers using an array of decimal digits. For example, we can represent the number 24681357 using this array:

int[] num = { 7, 5, 3, 1, 8, 6, 4, 2 };    // 24681357

In this example, the least significant digit (7) is stored in the first array element num[0]. This is a convenient representation.

This particular integer would fit in 32 bits. But we can use this same technique to store integers of arbitrary size, well beyond the capacity of a 32-bit or 64-bit integer.

We can perform arithmetic on large integers using the same techniques we learned in grade school. For example, consider these numbers:

int[] num1 = { 7, 5, 3, 1, 8, 6, 4, 2 };   // 24681357
int[] num2 = { 6, 8, 2, 5, 9 };            //    95286

If we want to compute num1 + num2, we first add 7 + 6 = 13. This means that the last digit of the sum is 13 % 10 = 3. We carry the 1, and now add 1 + 5 + 8 = 14. Now the next digit is 14 % 10 = 4, and so on.

When we add or multiply numbers by hand, generally we carry only one digit at a time. But when we add or multiply large numbers in a program, we can carry values with multiple digits! For example, suppose that we have

int[] num1 = { 7, 5, 3, 1, 8, 6, 4, 2 };   // 24681357

and we wish to compute the sum (num1 + 4829). We do not need to break the number 4829 apart into its own digit array! Instead, we first add 7 + 4829 = 4836. Now the last digit of the sum is 4836 % 10 = 6. We now carry the value 4836 / 10 = 483. This is a multi-digit carry. Now we continue: 5 + 483 = 488. So the next digit is 488 % 10 = 8, and we carry the value 488 / 10 = 48. And so on.

Similarly, we can use multi-digit carries to multiply a large integer by a value that is greater than 9. For example, if we want to compute the product (num1 * 4829), we first compute 7 * 4829 = 33803. The last digit of the product will be 3, and we will carry the multi-digit value 3380. See if you can figure out how to proceed from here.