Given an array arr[], the task is to check whether given array can be converted into a strictly decreasing sequence with the help of the below operation:
- Decrease any element(if it is greater than 1) by 1 in one operation
Examples:
Input: arr[] = {11, 11, 11, 11}
Output : Yes
Explanation:
The given sequence can be converted into
arr[] = {11, 10, 9, 8}
Input: arr[] = {1, 1}
Output: No
Explanation:
The given sequence cannot be converted into strictly decreasing sequence
Approach: The idea is to check whether every element of the array is greater than or equal to (N – index of element), because if it is greater than or equal to (N – index of element) that means array can be converted into [N, N-1, N-2, ….1]
Below is the implementation of the above approach:
C++
// C++ implementation to check that// array can be converted into a// strictly decreasing sequence#include <bits/stdc++.h>using namespace std;// Function to check that array // can be converted into a// strictly decreasing sequencebool check(int* arr, int n){ bool flag = true; // Loop to check that each element is // greater than the (N - index) for (int i = 0; i < n; i++) { // If element is less than (N - index) if (arr[i] < n - i) { flag = false; } } // If array can be converted if (flag) { return true; } else { return false; }}// Driver Codeint main(){ int arr1[] = { 11, 11, 11, 11 }; int n1 = sizeof(arr1) / sizeof(arr1[0]); // Function calling if (check(arr1, n1)) { cout << "Yes" << endl; } else { cout << "No" << endl; }} |
Java
// Java implementation to check that// array can be converted into a// strictly decreasing sequenceclass GFG{// Function to check that array // can be converted into a// strictly decreasing sequencestatic boolean check(int []arr, int n){ boolean flag = true; // Loop to check that each element is // greater than the (N - index) for (int i = 0; i < n; i++) { // If element is less than (N - index) if (arr[i] < n - i) { flag = false; } } // If array can be converted if (flag) { return true; } else { return false; }}// Driver Codepublic static void main(String[] args){ int arr1[] = { 11, 11, 11, 11 }; int n1 = arr1.length; // Function calling if (check(arr1, n1)) { System.out.print("Yes" + "\n"); } else { System.out.print("No" + "\n"); }}}// This code is contributed by amal kumar choubey |
Python3
# Python3 implementation to check that# array can be converted into a# strictly decreasing sequence# Function to check that array# can be converted into a# strictly decreasing sequencedef check(arr, n): flag = True; # Loop to check that each element # is greater than the (N - index) for i in range(n): # If element is less than (N - index) if (arr[i] < n - i): flag = False; # If array can be converted if (flag): return True; else: return False;# Driver Codeif __name__ == '__main__': arr1 = [ 11, 11, 11, 11 ]; n1 = len(arr1); # Function calling if (check(arr1, n1)): print("Yes"); else: print("No");# This code is contributed by sapnasingh4991 |
C#
// C# implementation to check that// array can be converted into a// strictly decreasing sequenceusing System;class GFG{// Function to check that array // can be converted into a// strictly decreasing sequencestatic bool check(int []arr, int n){ bool flag = true; // Loop to check that each element is // greater than the (N - index) for(int i = 0; i < n; i++) { // If element is less than (N - index) if (arr[i] < n - i) { flag = false; } } // If array can be converted if (flag) { return true; } else { return false; }}// Driver Codestatic public void Main(String[] args){ int []arr1 = { 11, 11, 11, 11 }; int n1 = arr1.Length; // Function calling if (check(arr1, n1)) { Console.Write("Yes" + "\n"); } else { Console.Write("No" + "\n"); }}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript implementation to check that// array can be converted into a// strictly decreasing sequence// Function to check that array// can be converted into a// strictly decreasing sequencefunction check(arr,n){ var flag = true; // Loop to check that each element is // greater than the (N - index) for (let i = 0; i < n; i++) { // If element is less than (N - index) if (arr[i] < n - i) { flag = false; } } // If array can be converted if (flag) { return true; } else { return false; }} let arr1= [ 11, 11, 11, 11 ]; let n1 = arr1.length; // Function calling if (check(arr1, n1)) { document.write("Yes"); } else { document.write("No"); } // This code is contributed by vaibhavrabadiya117.</script> |
Output:
Yes
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
