Count strictly decreasing subarrays
Here given code implementation process.
// C Program
// Count strictly decreasing subarrays
#include <stdio.h>
// Display given array elements
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
void countDecreasingArr(int arr[], int n)
{
int count = 0;
int dp[n];
// Set zero to all slot
for (int i = 0; i < n; ++i)
{
dp[i] = 0;
}
for (int i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
printArr(arr, n);
printf(" Decreasing subarrays : %d \n", count);
}
int main()
{
// Arrays
int a[] = {
1 , 2 , 1 , 0 , 2 , 1 , 6 , 4 , 2
};
int b[] = {
2 , 4 , 6 , 7
};
int c[] = {
5 , 5 , 2 , 4 , 6 , 7
};
// Get the size
int l1 = sizeof(a) / sizeof(a[0]);
int l2 = sizeof(b) / sizeof(b[0]);
int l3 = sizeof(c) / sizeof(c[0]);
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
countDecreasingArr(c, l3);
return 0;
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
/*
Java Program
Count strictly decreasing subarrays
*/
public class Subarrays
{
// Display given array elements
public void printArr(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
public void countDecreasingArr(int[] arr, int n)
{
int count = 0;
int[] dp = new int[n];
// Set zero to all slot
for (int i = 0; i < n; ++i)
{
dp[i] = 0;
}
for (int i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
printArr(arr, n);
System.out.print(" Decreasing subarrays : " + count + " \n");
}
public static void main(String[] args)
{
Subarrays task = new Subarrays();
int[] a = {
1 , 2 , 1 , 0 , 2 , 1 , 6 , 4 , 2
};
int[] b = {
2 , 4 , 6 , 7
};
int[] c = {
5 , 5 , 2 , 4 , 6 , 7
};
// Get the size
int l1 = a.length;
int l2 = b.length;
int l3 = c.length;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Count strictly decreasing subarrays
*/
class Subarrays
{
public:
// Display given array elements
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
void countDecreasingArr(int arr[], int n)
{
int count = 0;
int dp[n];
// Set zero to all slot
for (int i = 0; i < n; ++i)
{
dp[i] = 0;
}
for (int i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
this->printArr(arr, n);
cout << " Decreasing subarrays : " << count << " \n";
}
};
int main()
{
Subarrays *task = new Subarrays();
int a[] = {
1 , 2 , 1 , 0 , 2 , 1 , 6 , 4 , 2
};
int b[] = {
2 , 4 , 6 , 7
};
int c[] = {
5 , 5 , 2 , 4 , 6 , 7
};
// Get the size
int l1 = sizeof(a) / sizeof(a[0]);
int l2 = sizeof(b) / sizeof(b[0]);
int l3 = sizeof(c) / sizeof(c[0]);
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task->countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task->countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task->countDecreasingArr(c, l3);
return 0;
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
// Include namespace system
using System;
/*
Csharp Program
Count strictly decreasing subarrays
*/
public class Subarrays
{
// Display given array elements
public void printArr(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public void countDecreasingArr(int[] arr, int n)
{
int count = 0;
int[] dp = new int[n];
// Set zero to all slot
for (int i = 0; i < n; ++i)
{
dp[i] = 0;
}
for (int i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
this.printArr(arr, n);
Console.Write(" Decreasing subarrays : " + count + " \n");
}
public static void Main(String[] args)
{
Subarrays task = new Subarrays();
int[] a = {
1 , 2 , 1 , 0 , 2 , 1 , 6 , 4 , 2
};
int[] b = {
2 , 4 , 6 , 7
};
int[] c = {
5 , 5 , 2 , 4 , 6 , 7
};
// Get the size
int l1 = a.Length;
int l2 = b.Length;
int l3 = c.Length;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
package main
import "fmt"
/*
Go Program
Count strictly decreasing subarrays
*/
// Display given array elements
func printArr(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
fmt.Print("\n")
}
func countDecreasingArr(arr[] int, n int) {
var count int = 0
// Set zero to all slot
var dp = make([] int, n)
for i := 1 ; i < n ; i++ {
if arr[i - 1] > arr[i] {
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1
// Add counter
count += dp[i]
}
}
printArr(arr, n)
fmt.Print(" Decreasing subarrays : ", count, " \n")
}
func main() {
var a = [] int {
1,
2,
1,
0,
2,
1,
6,
4,
2,
}
var b = [] int {
2,
4,
6,
7,
}
var c = [] int {
5,
5,
2,
4,
6,
7,
}
// Get the size
var l1 int = len(a)
var l2 int = len(b)
var l3 int = len(c)
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
countDecreasingArr(a, l1)
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
countDecreasingArr(b, l2)
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
countDecreasingArr(c, l3)
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
<?php
/*
Php Program
Count strictly decreasing subarrays
*/
class Subarrays
{
// Display given array elements
public function printArr($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$arr[$i]);
}
echo("\n");
}
public function countDecreasingArr($arr, $n)
{
$count = 0;
// Set zero to all slot
$dp = array_fill(0, $n, 0);
for ($i = 1; $i < $n; ++$i)
{
if ($arr[$i - 1] > $arr[$i])
{
// When decreasing subarray occurs
$dp[$i] = $dp[$i - 1] + 1;
// Add counter
$count += $dp[$i];
}
}
$this->printArr($arr, $n);
echo(" Decreasing subarrays : ".$count." \n");
}
}
function main()
{
$task = new Subarrays();
$a = array(1, 2, 1, 0, 2, 1, 6, 4, 2);
$b = array(2, 4, 6, 7);
$c = array(5, 5, 2, 4, 6, 7);
// Get the size
$l1 = count($a);
$l2 = count($b);
$l3 = count($c);
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
$task->countDecreasingArr($a, $l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
$task->countDecreasingArr($b, $l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
$task->countDecreasingArr($c, $l3);
}
main();
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
/*
Node JS Program
Count strictly decreasing subarrays
*/
class Subarrays
{
// Display given array elements
printArr(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
countDecreasingArr(arr, n)
{
var count = 0;
// Set zero to all slot
var dp = Array(n).fill(0);
for (var i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
this.printArr(arr, n);
console.log(" Decreasing subarrays : " + count );
}
}
function main()
{
var task = new Subarrays();
var a = [1, 2, 1, 0, 2, 1, 6, 4, 2];
var b = [2, 4, 6, 7];
var c = [5, 5, 2, 4, 6, 7];
// Get the size
var l1 = a.length;
var l2 = b.length;
var l3 = c.length;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
main();
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
# Python 3 Program
# Count strictly decreasing subarrays
class Subarrays :
# Display given list elements
def printArr(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1
print(end = "\n")
def countDecreasingArr(self, arr, n) :
count = 0
# Set zero to all slot
dp = [0] * (n)
i = 1
while (i < n) :
if (arr[i - 1] > arr[i]) :
# When decreasing sublist occurs
dp[i] = dp[i - 1] + 1
# Add counter
count += dp[i]
i += 1
self.printArr(arr, n)
print(" Decreasing subarrays : ", count ," ")
def main() :
task = Subarrays()
a = [1, 2, 1, 0, 2, 1, 6, 4, 2]
b = [2, 4, 6, 7]
c = [5, 5, 2, 4, 6, 7]
# Get the size
l1 = len(a)
l2 = len(b)
l3 = len(c)
# Test A
# arr = [1,2,1,0,2,1,6,4,2]
# --------------------------
# ➀ [2,1]
# ➁ [2,1,0]
# ➂ [1,0]
# ➃ [2,1]
# ➄ [6,4]
# ➅ [4,2]
# ➆ [6,4,2]
# ---------------
# Total : 7
task.countDecreasingArr(a, l1)
# Test B
# arr = [5,5,2,4,6,7]
# --------------------------
# No decreasing sublist
# ---------------
# Total : 0
task.countDecreasingArr(b, l2)
# Test C
# arr = [5,5,2,4,6,7]
# --------------------------
# ➀ [5,2]
# ---------------
# Total : 1
task.countDecreasingArr(c, l3)
if __name__ == "__main__": main()
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
# Ruby Program
# Count strictly decreasing subarrays
class Subarrays
# Display given array elements
def printArr(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end
print("\n")
end
def countDecreasingArr(arr, n)
count = 0
# Set zero to all slot
dp = Array.new(n) {0}
i = 1
while (i < n)
if (arr[i - 1] > arr[i])
# When decreasing subarray occurs
dp[i] = dp[i - 1] + 1
# Add counter
count += dp[i]
end
i += 1
end
self.printArr(arr, n)
print(" Decreasing subarrays : ", count ," \n")
end
end
def main()
task = Subarrays.new()
a = [1, 2, 1, 0, 2, 1, 6, 4, 2]
b = [2, 4, 6, 7]
c = [5, 5, 2, 4, 6, 7]
# Get the size
l1 = a.length
l2 = b.length
l3 = c.length
# Test A
# arr = [1,2,1,0,2,1,6,4,2]
# --------------------------
# ➀ [2,1]
# ➁ [2,1,0]
# ➂ [1,0]
# ➃ [2,1]
# ➄ [6,4]
# ➅ [4,2]
# ➆ [6,4,2]
# ---------------
# Total : 7
task.countDecreasingArr(a, l1)
# Test B
# arr = [5,5,2,4,6,7]
# --------------------------
# No decreasing subarray
# ---------------
# Total : 0
task.countDecreasingArr(b, l2)
# Test C
# arr = [5,5,2,4,6,7]
# --------------------------
# ➀ [5,2]
# ---------------
# Total : 1
task.countDecreasingArr(c, l3)
end
main()
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
/*
Scala Program
Count strictly decreasing subarrays
*/
class Subarrays()
{
// Display given array elements
def printArr(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
def countDecreasingArr(arr: Array[Int], n: Int): Unit = {
var count: Int = 0;
// Set zero to all slot
var dp: Array[Int] = Array.fill[Int](n)(0);
var i: Int = 1;
while (i < n)
{
if (arr(i - 1) > arr(i))
{
// When decreasing subarray occurs
dp(i) = dp(i - 1) + 1;
// Add counter
count += dp(i);
}
i += 1;
}
printArr(arr, n);
print(" Decreasing subarrays : " + count + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subarrays = new Subarrays();
var a: Array[Int] = Array(1, 2, 1, 0, 2, 1, 6, 4, 2);
var b: Array[Int] = Array(2, 4, 6, 7);
var c: Array[Int] = Array(5, 5, 2, 4, 6, 7);
// Get the size
var l1: Int = a.length;
var l2: Int = b.length;
var l3: Int = c.length;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
import Foundation;
/*
Swift 4 Program
Count strictly decreasing subarrays
*/
class Subarrays
{
// Display given array elements
func printArr(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
func countDecreasingArr(_ arr: [Int], _ n: Int)
{
var count: Int = 0;
// Set zero to all slot
var dp: [Int] = Array(repeating: 0, count: n);
var i: Int = 1;
while (i < n)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
i += 1;
}
self.printArr(arr, n);
print(" Decreasing subarrays : ", count ," ");
}
}
func main()
{
let task: Subarrays = Subarrays();
let a: [Int] = [1, 2, 1, 0, 2, 1, 6, 4, 2];
let b: [Int] = [2, 4, 6, 7];
let c: [Int] = [5, 5, 2, 4, 6, 7];
// Get the size
let l1: Int = a.count;
let l2: Int = b.count;
let l3: Int = c.count;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
main();
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
/*
Kotlin Program
Count strictly decreasing subarrays
*/
class Subarrays
{
// Display given array elements
fun printArr(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
print("\n");
}
fun countDecreasingArr(arr: Array < Int > , n: Int): Unit
{
var count: Int = 0;
// Set zero to all slot
val dp: Array < Int > = Array(n)
{
0
};
var i: Int = 1;
while (i < n)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
i += 1;
}
this.printArr(arr, n);
print(" Decreasing subarrays : " + count + " \n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Subarrays = Subarrays();
val a: Array < Int > = arrayOf(1, 2, 1, 0, 2, 1, 6, 4, 2);
val b: Array < Int > = arrayOf(2, 4, 6, 7);
val c: Array < Int > = arrayOf(5, 5, 2, 4, 6, 7);
// Get the size
val l1: Int = a.count();
val l2: Int = b.count();
val l3: Int = c.count();
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment