Given an array of
N
integers, convert it into aZigZag
array by choosing any element and decrementing it by1
.What is a Zigzag Array
An array
A
is aZigZag
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:
We will solve this problem two times.
For the even-indexed array.
For the odd-indexed array.
Minimum
of both the solutions will be our desired solution.Start traversing the array, for each element find the
minimum
value among the element , previous element- 1
and next element- 1
.The difference between current element and calculated
minimum
value is the moves required to correctly position these three elements.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.