2

I have an array of booleans like this:

bool arr[] = { false, true, false, false, false, true };

I implemented an algorithm to find the next true value depending on the current index:

bool isNewRound = false;

int get_next_true(int index) {
    for(int i=index + 1; i<arr.size(); i++) {
        if (arr[i]) {
            return arr[i];
        }
    }
    
    isNewRound = true;

    for(int i=0; i<index; i++) {
        if (arr[i]) {
            return arr[i];
        }
    }

    return index;
}

I don't like my solution, because it uses two loops instead of one. I was thinking about using a while loop but in this case it requires an internal counter.

I need some optimization for the current solution, if that's possible, and maybe some suggestions on how to improve my approach.

P.S. It would be nice if I could detect that I already reached the end of the array.

Thank you

5
  • Have you heard of the modulo operator? Commented Nov 11, 2019 at 3:55
  • 1
    something like for(int i=index + 1; i != index; i = (i+1) % arr.size()) Commented Nov 11, 2019 at 3:55
  • @ThePhilomath looks awesomely working.. but can I also detect with bool that I have reached end of array once? Commented Nov 11, 2019 at 4:04
  • 2
    I don't understand whether you want to return the index of the next true value or that true value (why? it's literally always true) or something else. Commented Nov 11, 2019 at 9:31
  • return arr[i]; should be return i; Commented May 6, 2021 at 19:24

3 Answers 3

3

Time complexity of your approach is O(n)


Query in time complexity O(1) solution

const int n = 6;
bool arr[n] = { false, true, false, false, false, true };
int next_index[n];

int get_next_true(int index) {
  return next_index[index];
}

int main() {
  int true_index = -1;
  for (int i = n - 1; i >= 0; i--) {
    next_index[i] = true_index;
    if (arr[i] == true)
      true_index = i;
  }
  for (int i = n - 1; i >= 0; i--) {
    if (next_index[i] == -1)
      next_index[i] = true_index;
    else
      break;
  }
  printf("%d\n", get_next_true(2));
}

Query in time complexity O(log2n) solution

You can maintain the prefix sum of arr (consider true as value 1) and then use binary search to find the index of the next true value.

A simple demonstration:

const int n = 6;
bool arr[n] = { false, true, false, false, false, true };
int prefix[n];
bool isNewRound = false;

int get_next_true(int index) {
  int pos = std::upper_bound(prefix + index + 1, prefix + n, prefix[index]) - prefix;
  if (pos != n)
    return pos;
  isNewRound = true;

  pos = std::upper_bound(prefix, prefix + index + 1, 0) - prefix;
  if (arr[pos] == false)
    return -1; // Not Found

  return pos;
}

Also, remember to do some pre-processing before calling get_next_true:

prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
  prefix[i] = arr[i] + prefix[i - 1];
}

Query and modify an element in time complexity O(log2n)

Note that if arr is not a fixed array (You may want to modify it), you will need to use some data structure like segment tree.

Sign up to request clarification or add additional context in comments.

12 Comments

Any reason why you guys gave it downvote? Since it is 100% correct and faster
Though i didn't down voted you but lemme explain why others did. Whenever you give answer , try to provide a minimal example so that others can get what you are trying to say. Don't provide the whole solution just the crux of your answer. After all this ain't a theory class. P.S. I upvoted this. :-)
Why is prefix array never filled?
@Croolman I added some explanation for that part, please check:D
1) It will be faster only if an array is long enough. 2) We have algorithms std::partial_sum and std::lower_bound, there is no need to write your own. 3) Repeating 6 three times is a bad thing to do. Use constexpr for n, and then write arr[n].
|
0

I don't understand the posted code intent, but if the task is

Find next array index with true value

A simple solution (testable here) could be

template <class It>
constexpr size_t find_index_of_next_true(It first, It last, size_t index)
{
    size_t size = std::distance(first, last);
    return size <= index
        ? size
        : std::distance(first, std::find(first + index + 1, last, true));
}

Which is O(N), of course, as that is the time complexity of std::find, but the OP didn't mention how big their array is.

Comments

-1

Time complexity O(1) with O(N) extra space

First, we can store all the indices where the array holds true values and thus have a constant time access to the next index. Pre-processing (constructing an array of indices) still takes linear time, so this approach makes sense when you want to iterate through your true indices many times.

This code shows a static version, while dynamic will require O(N) time to modify values in the array.

#include <array>
#include <vector>

template <unsigned N>
class BoolArray {
public:
  using true_iterator = std::vector<unsigned>::const_iterator;

  BoolArray(std::array<bool, N> &&Init) : Data(std::move(Init)) {
    init();
  }

  true_iterator tbegin() const {
    return TrueValues.begin();
  }

  true_iterator tend() const {
    return TrueValues.end();
  }

  bool operator[](unsigned Index) {
    return Data[Index];
  }

private:
  void init() {
    TrueValues.reserve(N);
    // O(N) time to pre-process the data
    for (unsigned i = 0; i < N; ++i) {
      if (Data[i]) {
        TrueValues.push_back(i);
      }
    }
  }

  std::array<bool, N> Data;
  // extra O(N) space for fast fetching of the next index
  std::vector<unsigned> TrueValues;
};

Time complexity O(N) with O(1) extra space

This is a more straightforward approach. Iterate further where we left off and iterate all the way till the end.

Implemented iterator is only a prototype and can be implemented to be bidirectional.

#include <array>

template <unsigned N>
class BoolArray {
public:
  BoolArray(std::array<bool, N> &&Init) : Data(std::move(Init)) {}

  class true_iterator : public std::forward_iterator_tag {
  public:
    true_iterator(const true_iterator &) = default;
    true_iterator &operator=(const true_iterator &) = default;
    true_iterator(true_iterator &&) = default;
    true_iterator &operator=(true_iterator &&) = default;

    unsigned operator*() const {
      // O(1) for random-access iterators, which is true for
      // array iterators (it's just a difference between indices)
      return std::distance(Data.begin(), Iterator);
    }

    true_iterator &operator++() {
      ++Iterator;
      skipFalseValues();
      return *this;
    }
    true_iterator &operator++(int) {
      true_iterator tmp(*this);
      operator++();
      return tmp;
    }

    bool operator==(const true_iterator& rhs) const {
      return Iterator == rhs.Iterator;
    }
    bool operator!=(const true_iterator& rhs) const {
      return Iterator != rhs.Iterator;
    }

  private:
    using UnderlyingIterator = typename std::array<bool, N>::const_iterator;

    void skipFalseValues() {
      // O(N) time to find next true element
      for (;Iterator != Data.end() and not *Iterator; ++Iterator) {};
    }

    friend class BoolArray<N>;
    true_iterator(const std::array<bool, N> &Data, UnderlyingIterator Current)
      : Data(Data), Iterator(Current) {
      skipFalseValues();
    }

    const std::array<bool, N> &Data;
    UnderlyingIterator Iterator;
  };

  true_iterator tbegin() const {
    return {Data, Data.begin()};
  }

  true_iterator tend() const {
    return {Data, Data.end()};
  }

  bool operator[](unsigned Index) {
    return Data[Index];
  }

private:
  std::array<bool, N> Data;
};

Test

In both cases, the following code:

int main() {
  constexpr unsigned Size = 6;
  BoolArray<Size> TestArray{ {false, true, false, false, false, true} };
  for (auto It = TestArray.tbegin(), End = TestArray.tend(); It != End; ++It) {
    std::cout <<
      (TestArray[*It] ? "true" : "false") << " at index " << *It << std::endl;
  }
}

produces this output:

true at index 1
true at index 5

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.