What is the use of abs() in this C code

Question

I have a piece of code which will find out the repeating elements in an array of size n where the elements satisfy 1 <= arr[i] <= n, the code is given below:

#include<stdio.h>
#include<stdlib.h>

void printTwoElements(int arr[], int size)
{
    int i;
    printf("\n The repeating element is");

    for(i = 0; i < size; i++)
    {
        if(arr[abs(arr[i])-1] > 0)
        {
            arr[abs(arr[i])-1] = -arr[abs(arr[i])-1];
        }
        else
        {
            printf(" %d ", abs(arr[i]));
        }
    }
}

/* Driver program to test above function */
int main()
{
    int arr[] = {7, 3, 4, 5, 5, 6, 2};
    int  n = sizeof(arr)/sizeof(arr[0]);
    printTwoElements(arr, n);
    return 0;
}

I would like to know the use of abs() in this given code?

Answer 1

If you had started with the most straightforward way to solve this, given additional O(n) space, you would have probably thought about storing "already encountered" flags in a separate (auxiliary) array to look them up afterwards:

// pseudocode (zero based indexing ignored for now)
for each value in array
   if (already_encountered[value] == true)
       print "found a duplicate of " + value
   else
       already_encountered[value] = true      

Your algorithm goes a little further. Given the fact that an integer is (probably) 32-bit, and you only need to store a limited (small) range of values, each array member actually has sufficient free bits to store the "already encountered" flag.

This means that you can drop the auxiliary already_encountered array given above, and use this extra space to store the flags with no extra memory allocation.

Using some bit twiddling, you could, for example, choose to store this value at the highest bit (leaving you with 31 bits to store your numbers). Whenever you want to check if the flag is set, you would need to extract this highest bit and check it, and then finally clear the bit before printing out the value:

// pseudocode (zero based indexing ignored)
for each value in array
{
   // this value might already have a flag previously encoded
   // for some other element, so remove it before continuing
   plain_value = remove_flag(value)

   // check if the flag is set for the actual value,
   // if not, set it now
   if (is_flag_set(array[plain_value]) == true)
       print "found a duplicate of " + plain_value
   else
       array[plain_value] = set_flag(array[plain_value])
}

The only thing left to do is to define set_flag, is_flag_set and remove_flag functions.

In your case, the algorithm "sets the flag" by negating the value, "tests for flag" by checking if the value is negative, and "removes the flag" by using the absolute value (hence the abs function).

This can be safely achieved because signed integers use a single bit to store their sign information, allowing the transformation to leave the original value intact (provided it is small enough).

This leaves you with your final C code:

void printTwoElements(int arr[], int size)
{
    int i;
    printf("\n The repeating element is");

    for(i = 0; i < size; i++)
    {
        // remove the flag
        int plain_value = abs(arr[i]);

        // is flag set?
        if(arr[plain_value-1] < 0)
        {
            printf(" %d ", plain_value);
        }
        else
        {
            // set the flag by negating
            arr[plain_value-1] = -arr[plain_value-1];                
        }
    }
}

Answer 2

In the course of the algorithm, some array entries are set to negative values as a marker. Therefore the entries' absolute value has to be taken when they are used as indices into the array.

In the hope of not spoiling anything:

The algorithm requires that the array entries of an n-element array all are between 1 and n inclusive. If any entry is larger than n or smaller than -n or 0, it will access invalid addresses, and if any element is negative, the marking logic will fail.

The logic of the algorithm is:

for each array element e:
    if the value at (e-1) is positive, e has not yet been seen,
                   negate the value at (e-1) to mark e as seen
    otherwise, e has already been seen, so print it

So since array entries become negative in the course of running the algorithm, the absolute value has to be taken to obtain valid indices.

Let us follow the algorithm for a modified example to see how it works:

before: arr = { 7, 3, 4, 5, 5, 3, 2}
i == 0: arr[0] = 7
        arr[7-1] is 2 > 0 ~> negate
        arr = { 7, 3, 4, 5, 5, 3, -2}
i == 1: arr[1] = 3
        arr[3-1] is 4 > 0 ~> negate
        arr = { 7, 3, -4, 5, 5, 3, -2}
i == 2: arr[2] is -4 ~> abs for indexing
        arr[4-1] is 5 > 0 ~> negate
        arr = { 7, 3, -4,-5, 5, 3, -2}
i == 3: arr[3] is -5 ~> abs for indexing
        arr[5-1] is 5 > 0 ~> negate
        arr = { 7, 3, -4, -5, -5, 3, -2}
i == 4: arr[4] is -5 ~> abs for indexing
        arr[5-1] is -5 < 0 ~> print abs(-5) as duplicate
i == 5: arr[5] is 3
        arr[3-1] is -4 < 0 ~> print abs(3) as duplicate
i == 6: arr[6] is -2 ~> abs for indexing
        arr[2-1] is 3 > 0 ~> negate
        arr = { 7, -3, -4, -5, -5, 3, -2}

        indices of positive entries: 0, 5 ~> 1 and 6 not in original array
        indices of negative entries: 1, 2, 3, 4, 6 ~> 2, 3, 4, 5, 7 in original array

Answer 3

abs() is the absolute value function in C. It makes sure your array index is not negative.

Answer 4

It's trying to ensure that the program never attempts a negative array index while walking through the elements.