0

I set myself a challenge of trying to make a program that detects if a given vector is a palindrome. Here is the code:

#include <iostream>
#include <vector>

bool isPalindromeArray(std::vector<int>& nums) {
    float size = nums.size()/2;
    int k = 0;

    if(size = int(size)) {
        for(int i = 0; i < size; i++) {
            if(nums[i] == nums[nums.size() - i]) {
                k++;
                if(k == size) {
                    return true;
                }
            }
        }
    } else {
        for(int i = 0; i < int(size) - 1 ; i++) {
            if(nums[i] == nums[(int(size) - 1) - i]) {
                k++;
                if(k == int(size) - 1) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    std::vector<int> arr;
    arr.push_back(1);
    arr.push_back(2);
    arr.push_back(3);
    arr.push_back(2);
    arr.push_back(1);

    if(isPalindromeArray(arr)) {
        std::cout << "My Code Works";
    }
}

When I run the code, it returns false no matter if the vector has an odd or even number of values. I have tried various troubleshooting steps but I can't seem to make it work.

(MinGW64, Windows 10, VS Code)

Noah Burchell
  • 31
  • 7
  • 3
    Related: Take note of [`begin()`](https://en.cppreference.com/w/cpp/container/vector/begin) / [`end()`](https://en.cppreference.com/w/cpp/container/vector/end) and [`rbegin()`](https://en.cppreference.com/w/cpp/container/vector/rbegin) / [`rend()`](https://en.cppreference.com/w/cpp/container/vector/rend), which would *massively* reduce the complexity of your code. – DevSolar Mar 11 '22 at 11:01
  • @DevSolar haha I completely forgot about that when writing this but yeah that would be a good idea... Thanks! – Noah Burchell Mar 11 '22 at 11:03
  • 1
    `float` for indexing is pretty inefficient. Why all that floating point math when simple integer math just fits as nicely? – Aconcagua Mar 11 '22 at 11:04
  • @Aconcagua it was the only way I could think to detect if it was an odd odd even number. – Noah Burchell Mar 11 '22 at 11:06
  • 1
    `int n = 7; if(n % 2 == 0) { /* even */ } else { /* odd */ }` – or bitwise and with 1 for the same effect... In any case you wouldn't even need to know, either with iterators or with indices, you start with `auto b = v.begin(); auto e = std::prev(v.end();)` and while `b` is smaller than `e` you yet need to check for equality (`*b == *e`; analogously if using indices). Note that `std::prev(v.end());` is UB if the vector is empty, so you need to check that first. – Aconcagua Mar 11 '22 at 11:13
  • 3
    With [`std::equal`](https://en.cppreference.com/w/cpp/algorithm/equal), `return std::equal{nums.begin(), nums.end(), nums.rbegin(), nums.rend()};` :-) – Jarod42 Mar 11 '22 at 11:17
  • Side note: `if(size = (int)size)` is `true` for *any* value but `(int)size` being zero, as this is an assignment. You need `==` instead. Be aware that with exception of a few rare special cases you shouldn't ever compare floating point values for exact equality (`==`), as floating point suffers from rounding issues, so you need instead to check for the difference of two values being smaller than some appropriately defined epsilon (see e.g. [here](https://stackoverflow.com/questions/4915462/how-should-i-do-floating-point-comparison). – Aconcagua Mar 11 '22 at 11:19
  • Your approach, however, is such a special case, as you have either exact integral values or just one single binary decimal for 2^-1, which *could* be represented exactly. Still it remains inefficient. – Aconcagua Mar 11 '22 at 11:21
  • @Jarod42 Nice, elegant, but compares values twice. Some doubts about that being allowed to use (homework?). – Aconcagua Mar 11 '22 at 11:23
  • @Aconcagua: Then replace `end()` by `begin() + size() / 2`. but probably not allowed for homework indeed. – Jarod42 Mar 11 '22 at 12:21

2 Answers2

11

It is highly recommended if you learn how to use algorithms delivered by standard library:

template <typename T>
bool is_palindrome(const T& container)
{
    return std::equal(std::begin(container),
        std::begin(container) + std::size(container) / 2,
        std::rbegin(container));
}

Live test

Marek R
  • 32,568
  • 6
  • 55
  • 140
  • This is the idiomatic C++ solution! – DevSolar Mar 11 '22 at 11:29
  • 2
    Might be worth pointing out that the integer division effect of `/ 2` means the middle element of an odd-length sequence is not considered, which of course is the correct thing to do; pop and poop are both palindromic. – Bathsheba Mar 11 '22 at 11:54
  • It wouldn't really matter if you did compare the middle element, since you'd compare it against itself. – MSalters Mar 11 '22 at 12:47
  • 1
    @MSalters: Would be sloppy though. And would break `{1.0, NaN, 1.0}`. – Bathsheba Mar 11 '22 at 13:06
  • @Bathsheba `NaN` is out anyway, what about `{1.0, NaN, 1.0, NaN, 1.0}`? Agree on the sloppy part, though. – Aconcagua Mar 11 '22 at 13:08
  • @Aconcagua: But at least that is more reasonable. I guess it's down to if you define `{T t}` as a palindrome for any type `T` and any value `t`. I'd be inclined to. – Bathsheba Mar 11 '22 at 13:23
1

The behaviour of the following line is undefined by the C++ standard:

if (nums[i] == nums[nums.size() - i])

..as the vector subscript is out of range because:

nums[nums.size() - i]

..which, for the first loop, means:

nums[5]

..which is definitely out of range. So just add a -1 to nums.size() - i:

nums[nums.size() - i - 1]

This will print out "My Code Works" (i.e., return true) when a std::vector is palindrome.

Also, this will be a shorter and better version of your code:

bool isPalindromeArray(std::vector<int>& nums) {
    int size = nums.size() / 2;

    for (int i = 0; i < size; i++) {
        if (nums[i] != nums[nums.size() - i - 1]) {
            return false;
        }
    }
    return true;
}
Bathsheba
  • 231,907
  • 34
  • 361
  • 483
The Coding Fox
  • 1,488
  • 1
  • 4
  • 18