Horje
Find total number of positions in all Subarrays such that position and value are same

Given an array A[] of size N, the task is to find the total number of positions in all the subarrays such that the value and position are the same.

Examples:

Input: A[] = {1, 2}
Output: 3
?Explanation: Following are the subarrays:

In the subarray A[1, 1] = [1], elementat position 1 is 1.
In the subarray A[1, 2] = [1, 2], for both the elements the condition is satisfied.
In the subarray A[2, 2] = [2], element at position is 2 which is the only element.
Hence the total positions over all subarrays = 1 + 2 + 0 = 3.

Input: A[] = {1, 3, 4, 2}
Output: 5

Approach: The problem can be solved based on the following observation:

Fix some position 1 ? i ? N and a subarray A[L, R]

Further, the condition of i being a valid position is Ai = i ? L + 1. Rewriting this condition, we obtain L = i ? Ai + 1, in other words, there is exactly one choice of L given that i is symmetrical.
However, we must also have L ? 1, so i ? Ai + 1 ? 1? i ? Ai.
The choice of R doesn’t affect i being a symmetrical point, so any R such that R ? i works, and there are N ? i + 1 of these.

Our final answer is thus simply the sum of N ? i + 1 over all positions 1 ? i ? N such that Ai ? i.

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
#include <iostream>
using namespace std;
 
// Function to count total number
// of valid positions
int count(int arr[], int N)
{
    int temp = 0;
    for (int i = 0; i < N; i++) {
        if (arr[i] <= i + 1)
            temp = temp + N - i;
    }
    return temp;
}
 
int main()
{
    int A[] = { 1, 2 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function call
    cout << count(A, N);
 
    return 0;
}
 
// This code is contributed by arohirai2616.

Java

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
public class GFG {
 
    // Function to count total number
    // of valid positions
    public static int count(int arr[], int N)
    {
        int temp = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] <= i + 1)
                temp = temp + N - i;
        }
        return temp;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int A[] = { 1, 2 };
        int N = A.length;
 
        // Function call
        System.out.println(count(A, N));
    }
}

Python3

# Python3 code to implement the approach
 
# Function to count total number
# of valid positions
def count(arr, N):
 
    temp = 0
    for i in range(0, N):
        if (arr[i] <= i + 1):
            temp = temp + N - i
    return temp
 
# Driver code
A = [1, 2]
N = len(A)
 
# Function call
print(count(A, N))
 
# This code is contributed by arohirai2616.

C#

// C# code to implement the approach
using System;
 
public class GFG{
 static int count(int[] arr, int N)
{
    int temp = 0;
    for (int i = 0; i < N; i++) {
        if (arr[i] <= i + 1)
            temp = temp + N - i;
    }
    return temp;
}
 
    public static void Main (){
    int[] A = {1, 2};
    int N = A.Length;
 
    // Function call
    Console.Write(count(A, N));
    }
}
 
// This code is contributed by ksam24000.

Javascript

<script>
// Javascript code to implement the approach
 
// Function to count total number
// of valid positions
function count( arr, N)
    {
        let temp = 0;
        for (let i = 0; i < N; i++) {
            if (arr[i] <= i + 1)
                temp = temp + N - i;
        }
        return temp;
    }
     
    // Driver code
let A = [ 1, 2 ];
let N = A.length;
 
// Function call
console.log(count(A, N));
 
// This code is contributed by arohirai2616.
</script>

Output

3

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


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Find Array after removing -1 and closest non-negative left element Find Array after removing -1 and closest non-negative left element
Find original Array from given Array of GCD of prefix Find original Array from given Array of GCD of prefix
Count of Pairs such that modulo of product of one with their XOR and X is 1 Count of Pairs such that modulo of product of one with their XOR and X is 1
Check if Array can be made strictly increasing by replacing element with Average of adjacents Check if Array can be made strictly increasing by replacing element with Average of adjacents
Lexicographical smallest and largest Permutation from Array whose elements are max of Prefix Lexicographical smallest and largest Permutation from Array whose elements are max of Prefix

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje