Tell me the Input in which this code will give incorrect Output

Question

There's a problem, which I've to solve in c++. I've written the whole code and it's working in the given test cases but when I'm submitting it, It's saying wrong answer. I can't understand that why is it showing wrong answer. I request you to tell me an input for the given code, which will give incorrect output so I can modify my code further.

Shrink The Array

You are given an array of positive integers A[] of length L. If A[i] and A[i+1] both are equal replace them by one element with value A[i]+1. Find out the minimum possible length of the array after performing such operation any number of times.

Note: After each such operation, the length of the array will decrease by one and elements are renumerated accordingly.

Input format:

• The first line contains a single integer L, denoting the initial length of the array A.
• The second line contains L space integers A[i] − elements of array A[].

Output format:

• Print an integer - the minimum possible length you can get after performing the operation described above any number of times.

Example:

Input

7
3 3 4 4 4 3 3

Output

2

Sample test case explanation

3 3 4 4 4 3 3 -> 4 4 4 4 3 3 -> 4 4 4 4 4 -> 5 4 4 4 -> 5 5 4 -> 6 4.

Thus the length of the array is 2.

My code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
  bool end = false;
  int l;
  cin >> l;

  int arr[l];
  for(int i = 0; i < l; i++){

    cin >> arr[i];
  }
  int len = l, i = 0;

  while(i < len - 1){
    if(arr[i] == arr[i + 1]){
        arr[i] = arr[i] + 1;
        if((i + 1) <= (len - 1)){
            for(int j = i + 1; j < len - 1; j++){
                arr[j] = arr[j + 1];
            }
        }
        len--;
        i = 0;
    }
    else{
        i++;
    }
  }
  cout << len;
  return 0;
}

THANK YOU

Answer 1

As noted in the comments: Just picking the first two neighbours that have the same value and combining those will lead to suboptimal results.

You will need to investigate which two neighbours you should combine somehow. When you have combined two neighbours you then need to investigate which neighbours to combine on the next level. The number of combinations may become plentiful.

One way to solve this is through recursion.

If you've followed the advice in the comments, you now have all your input data in std::vector<unsigned> A(L).

You can now do std::cout << solve(A) << '\n'; where solve has the signature size_t solve(const std::vector<unsigned>& A) and is described below:

• Find the indices of all neighbour pairs in A that has the same values and put the indices in a std::vector<size_t> neighbours. Example: If A contains 2 2 2 3, put 0 and 1 in neighbours.

• If no neighbours are found (neighbours.empty() == true), return A.size().

• Define a minimum variable and initialize it with A.size() - 1 which is the worst result you know you can get at this point. So, size_t minimum = A.size() - 1;

• Loop over all indices stored in neighbours (for(size_t idx : neighbours))

  • Copy A into a new std::vector<unsigned>. Let's call it cpy.
  • Increase cpy[idx] by one and remove cpy[idx+1].
  • Call size_t result = solve(cpy). This is where recursion comes in.
  • Is result less than minimum? If so assign result to minimum.

• Return minimum.

---

_{I don't think I ruined the programming exercise by providing one algorithm for solving this. It should still have plenty of things to deal with. Recursion won't be possible with big data etc.}