Array ZigZag

CONCEPTS USED:

Arrays

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

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:

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.