Subarray permutation that satisfies the given condition | C ++ implementation of the approach ; Function that returns true if the required subarray exists in the given array ; Map to store the positions of each integer in the original permutation ; To store the address of each entry in arr [ n ] but with 1 - based indexing ; To track minimum position sumcur for sum of all positions till this position ; Summing up addresses ; Tracking minimum address encountered till now ; The sum of the addresses if it forms the required subarray ; If current sum of address is equal to val ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long int ll ; bool subArray ( ll * arr , ll n , ll m ) { ll i ; unordered_map < ll , ll > mp ; for ( i = 0 ; i < n ; i ++ ) { mp [ arr [ i ] ] = i + 1 ; } ll sumcur = 0 ; ll p = INT_MAX ; vector < ll > ans ; for ( i = 1 ; i <= m ; i ++ ) { sumcur += mp [ i ] ; p = min ( p , mp [ i ] ) ; ll val = p * i - i + ( i * ( i + 1 ) ) / 2 ; if ( i == m ) { if ( val == sumcur ) { return true ; } else return false ; } } } int main ( ) { ll arr [ ] = { 4 , 5 , 1 , 3 , 2 , 6 } ; int n = sizeof ( arr ) / sizeof ( int ) ; ll m = 3 ; if ( subArray ( arr , n , m ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }