Consecutive Numbers - C++ Solution

1. Introduction

In this blog post, we will discuss a common problem in array processing: determining whether a given integer array contains only consecutive numbers. This problem tests one's understanding of array manipulation and hash sets in C++.

Problem

The task is to check if an array contains only consecutive integers. The elements in the array can appear in any order, and negative numbers are also allowed.

Examples:

- Input: [-1, 5, 4, 2, 0, 3, 1]

Output: true

- Input: [4, 2, 4, 3, 1]

Output: false

- Input: [2, 5, 3, 1]

Output: false

2. Solution Steps

1. Find the minimum and maximum values in the array.

2. Check if the array's length is equal to the difference between the maximum and minimum values plus one.

3. Use a hash set to check for duplicate elements.

4. If the array length matches the range and no duplicates are found, return true. Otherwise, return false.

3. Code Program

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// Function to check if the array contains only consecutive numbers
bool areConsecutive(vector<int>& nums) {
    if (nums.empty()) return false; // Handle empty array

    int minVal = nums[0], maxVal = nums[0];
    unordered_set<int> seen;

    // Find the minimum and maximum values and check for duplicates
    for (int num : nums) {
        if (seen.find(num) != seen.end()) return false; // Duplicate found
        seen.insert(num);
        minVal = min(minVal, num);
        maxVal = max(maxVal, num);
    }

    // Check if the length matches the range of numbers
    return (maxVal - minVal + 1 == nums.size());
}

int main() {
    vector<int> nums = {-1, 5, 4, 2, 0, 3, 1};
    cout << "Contains only consecutive numbers: " << boolalpha << areConsecutive(nums) << endl;
    return 0;
}

Output:

Contains only consecutive numbers: true

Explanation:

The function areConsecutive starts by finding the minimum and maximum values in the array and uses a hash set to check for duplicates. If the length of the array is equal to the range (max - min + 1) and no duplicates are found, it indicates that the array contains only consecutive numbers. In the given examples, the function accurately determines the nature of the arrays based on these criteria.


Comments