# How to Convert an Array into Zigzag Array? Given an array of `N` integers, convert it into a `ZigZag` array by choosing any element and decrementing it by `1`.

## An array `A` is a `ZigZag` array if either: 1. Every even-indexed element is greater than its adjacent elements, ie. `A0 > A1 < A2 > A3 < A4 > ...` 2. OR, every odd-indexed element is greater than its adjacent elements, ie. `A0 < A1 > A2 < A3 > A4 < ...`Print the minimum number of moves to transform the given array into a `ZigZag` array.

See original problem statement here

#### For Example:

``````Input: N = 3
A[] = [2, 3, 4]

Output: 2

Explanation:

We can decrease 3 to 1 to form [2, 1, 4] so that all even indexed elements are greater than the neighbours. Hence output is 2.``````

## Solving Approach for Zigzag Array:

1. We will solve this problem two times.

1. For the even-indexed array.

2. For the odd-indexed array.

2. `Minimum` of both the solutions will be our desired solution.

3. Start traversing the array, for each element find the `minimum` value among the element , previous element `- 1` and next element `- 1`.

4. The difference between current element and calculated `minimum` value is the moves required to correctly position these three elements.

5. Similarly, keep doing it for the entire array and keep track of a `sum` variable.

`sum` `+= ( A[i] - min(A[i],A[i-1]-1,A[i+1]-1) )`

### SOLUTIONS:

```#include <stdio.h>

int solve(int arr[],int n,int start)
{
int res = 0;
for(int i=start;i<n;i+=2)
{
int to = arr[i];
if(i)
// make sure current element is less than its left neighboor
{
if(arr[i-1]-1<to)
to = arr[i-1]-1;
}
if(i+1 != n)
// make sure current element is less than its right neighboor
{
if(arr[i+1]-1<to)
to = arr[i+1]-1;
}
// if curr value was decreased to "to", add the difference
res += arr[i] - to;
}
return res;
}

int main()
{
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
int res1 = solve(arr,n,0);
int res2 = solve(arr,n,1);

if(res1 < res2)
printf("%d",res1);
else
printf("%d",res2);

return 0;
}

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

int solve(int arr[],int n,int start)
{
int res = 0;
for(int i=start;i<n;i+=2)
{
int to = arr[i];
if(i){
// make sure current element is less than its left neighboor
to = min(to,arr[i-1]-1);
}
if(i+1 != n){
// make sure current element is less than its right neighboor
to = min(to,arr[i+1]-1);
}
// if curr value was decreased to "to", add the difference
res += arr[i] - to;
}
return res;
}

int main()
{
int n;cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];

cout<<min(solve(arr,n,0),solve(arr,n,1));

return 0;
}

```
```import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
static int solve(int arr[],int n,int start)
{
int res = 0;
for(int i=start;i<n;i+=2)
{
int to = arr[i];
if(i>0)
// make sure current element is less than its left neighboor
to = Math.min(to,arr[i-1]-1);
if(i+1 != n)
// make sure current element is less than its right neighboor
to = Math.min(to,arr[i+1]-1);
// if curr value was decreased to "to", add the difference
res += arr[i] - to;
}
return res;
}
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
arr[i] = sc.nextInt();

System.out.println(Math.min(solve(arr,n,0),solve(arr,n,1)));
}
}

```

[forminator_quiz id="436"]

Space Complexity: `O(1)`

This article tried to discuss Arrays. Hope this blog helps you understand and solve the problem. To practice more problems on backtracking you can check out MYCODE | Competitive Programming.