10

Check if given Array can be formed by increasing or decreasing element

 2 years ago
source link: https://www.geeksforgeeks.org/check-if-given-array-can-be-formed-by-increasing-or-decreasing-element/?utm_campaign=newhomepage
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Check if given Array can be formed by increasing or decreasing element

Given an array arr[] of length N with N integers.  Assume all the elements of array arr[] are equal to 0 and start with the first element. The task is to obtain the given array after performing the given operations on it.  At last, you must be there from where you start. Return 1 if it is possible to obtain the array arr[] after some operations (possibly zero) else print 0.

  • Increase the element at which you are by 1. Then move to the next element if exists.
  • Decrease the element at which you are by 1. Then move to the previous element if exists.

Examples:

Input: arr[] = {1, -1, 0}
Output: 1
Explanation: First the array arr[] is ={0, 0, 0} and you are on the first index i.e., 0. 
Move right by one, the element at index 0 is increased by 1 arr[] = {1, 0, 0}, Now, you are on index 1.
Move left by one, the element at index 1 is decreased by 1 arr[] = {1, -1, 0}, Now, you are on index 0.
The array arr[] can be achieved by a finite number of operations i.e., 2, So, print 1.

Input: arr[] = {3, -1, -2, 0}
Output: 1

Approach: 

The basic idea is to eliminate all the consecutive zeroes from the end of the array till we get a non-zero element and then perform the given operations.

Follow the below steps to solve the problem:

  • Initialize a variable prev = 0 and n = size of vector v.
  • Remove all the consecutive zeros from back till we get a non-zero element.
  • If the vector is empty it means all the elements were zeros so return 1.
  • If there is only one element left in the array
    • If the first element is less than equal to 0 or
    • If the last element is greater than 0, then return 0.
    • Else run a loop from n-1 to 1 index of the array and subtract v[i] from Prev.
      • If Prev is less than or equal to 0 at any point of time then return 0.
    • After executing the loop if Prev = v[0] then return 1, else return 0.

Below is the implementation of the above approach:

// C++ code to implement the above approach

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

// Function to find is it possible to make
// the array or not

bool solve(vector<int> v)
{

    ll prev = 0, n = v.size();

    // Remove all the consecutive zeros from back
    // till we get a non-zero element

    while (!v.empty() && v.back() == 0) {
        v.pop_back();
    }

    // All the elements were zeros so return 1

    if (v.empty()) {
        return 1;
    }

    // If there is only one element left in the array
    // or the first element is less than equal to 0
    // or the last element is greater than 0 then return 0

    if (v.size() == 1 || v[0] <= 0 || v.back() > 0) {
        return 0;
    }

    for (ll i = v.size() - 1; i > 0; i--) {
        prev = prev - v[i];

        if (prev <= 0)
            return 0;
    }

    if (prev == v[0])
        return 1;

    return 0;
}

// Driver Code

int main()
{

    vector<int> vec = { 1, -1, 0 };
    cout << solve(vec) << endl;

    vector<int> vec2 = { 3, -1, -2, 0 };
    cout << solve(vec2) << endl;

    vector<int> vec3 = { 1, 1, 1, 0 };
    cout << solve(vec3) << endl;

    return 0;
}
Output

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles:

2022-05-23-17-45-51-DSASP_In-Article%20Ad.webp

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK