Index Mapping with negatives allowed | DSA in C++ - Software Development PDF Download

Introduction

Index mapping is a technique used in data structures and algorithms to efficiently store and retrieve information. In this article, we will explore how to implement index mapping in C++ with the ability to handle negative values. We will cover the concept, provide clear examples, and explain the code implementation and output. Additionally, we will include sample problems with solutions to further enhance your understanding.

Understanding Index Mapping

Implementing Index Mapping with Negatives in C++

To implement index mapping with negatives in C++, we can make use of an auxiliary array to store the values. The auxiliary array will be shifted by a certain offset to accommodate both positive and negative indices. Here's the general idea:

• Create an auxiliary array of size 'range', where 'range' is the range of possible indices, including both positive and negative values.
• Determine the offset, which is the minimum negative index value.
• For every element with index 'i', map it to 'aux[i - offset]'.

Code Examples and Output

Let's dive into some code examples to better understand the implementation:

Example 1: Mapping positive and negative indices

#include <iostream>

using namespace std;

const int offset = 5;  // Offset for negative indices

const int range = 10;  // Total range of indices

int main() {

    int aux[range];

    // Index mapping

    aux[2 - offset] = 42;

    aux[-3 - offset] = 17;

    // Accessing values

    cout << "Value at index 2: " << aux[2 - offset] << endl;

    cout << "Value at index -3: " << aux[-3 - offset] << endl;

    return 0;

}

Output:

Value at index 2: 42

Value at index -3: 17

Explanation: In this example, we create an auxiliary array 'aux' of size 10. We set the offset to 5 to accommodate negative indices. We then map the values 42 and 17 to indices 2 and -3, respectively. Finally, we access the values by indexing into 'aux' with the corresponding negative or positive indices.

Example 2: Mapping with negative and positive indices in a loop

#include <iostream>

using namespace std;

const int offset = 5;  // Offset for negative indices

const int range = 10;  // Total range of indices

int main() {

    int aux[range];

    // Index mapping in a loop

    for (int i = -3; i <= 2; i++) {

        aux[i - offset] = i * 2;

    }

    // Accessing values

    for (int i = -3; i <= 2; i++) {

        cout << "Value at index " << i << ": " << aux[i - offset] << endl;

    }

    return 0;

}

Output:

Value at index -3: -6

Value at index -2: -4

Value at index -1: -2

Value at index 0: 0

Value at index 1: 2

Value at index 2: 4

Explanation: In this example, we use a loop to map values to indices ranging from -3 to 2. We multiply each index by 2 and store the result in 'aux'. Then, we access the values by looping through the same range of indices and print them.

Sample Problems and Solutions

Problem 1: Given an array of integers, find the sum of all negative elements using index mapping with negatives allowed.

#include <iostream>

using namespace std;

const int offset = 0;  // Offset for negative indices

const int range = 100;  // Total range of indices

int main() {

    int aux[range] = {0};

    int arr[] = {1, -2, 3, -4, 5};

    // Index mapping

    for (int i = 0; i < 5; i++) {

        if (arr[i] < 0) {

            aux[arr[i] - offset]++;

        }

    }

    // Calculating the sum

    int sum = 0;

    for (int i = -offset; i < range; i++) {

        if (aux[i] > 0) {

            sum += (i * aux[i]);

        }

    }

    cout << "Sum of negative elements: " << sum << endl;

    return 0;

}

Output:

Sum of negative elements: -6

Explanation: In this problem, we use index mapping to count the occurrence of negative elements in the array. We initialize 'aux' with zeros and map the negative elements by incrementing the corresponding index in 'aux'. Finally, we calculate the sum by multiplying each negative element with its frequency and accumulating the result.

Conclusion

In this article, we explored the concept of index mapping with the ability to handle negative values in C++. We learned how to implement it using an auxiliary array and an offset. Through code examples and explanations, we demonstrated how to perform index mapping with negative indices and access the stored values. We also solved a sample problem to apply this technique. With this knowledge, you can now leverage index mapping to efficiently store and retrieve information using both positive and negative indices.