Find permutation of numbers upto N with a specific sum in a specific range | Function to check if sum is possible with remaining numbers ; Stores the minimum sum possible with x numbers ; Stores the maximum sum possible with x numbers ; If S lies in the range [ minSum , maxSum ] ; Function to find the resultant permutation ; Stores the count of numbers in the given segment ; If the sum is not possible with numbers in the segment ; Output - 1 ; Stores the numbers present within the given segment ; Iterate over the numbers from 1 to N ; If ( S - i ) is a positive non - zero sum and if it is possible to obtain ( S - i ) remaining numbers ; Update sum S ; Update required numbers in the segement ; Push i in vector v ; If sum has been obtained ; Break from the loop ; If sum is not obtained ; Output - 1 ; Stores the numbers which are not present in given segment ; Loop to check the numbers not present in the segment ; Pointer to check if i is present in vector v or not ; If i is not present in v ; Push i in vector v1 ; Point to the first elements of v1 and v respectively ; Print the required permutation ; Driver Code
def possible ( x , S , N ) : NEW_LINE INDENT minSum = ( x * ( x + 1 ) ) // 2 NEW_LINE maxSum = ( x * ( ( 2 * N ) - x + 1 ) ) // 2 NEW_LINE if ( S < minSum or S > maxSum ) : NEW_LINE INDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT def findPermutation ( N , L , R , S ) : NEW_LINE INDENT x = R - L + 1 NEW_LINE if ( not possible ( x , S , N ) ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE return NEW_LINE DEDENT else : NEW_LINE INDENT v = [ ] NEW_LINE for i in range ( N , 0 , - 1 ) : NEW_LINE INDENT if ( ( S - i ) >= 0 and possible ( x - 1 , S - i , i - 1 ) ) : NEW_LINE INDENT S = S - i NEW_LINE x -= 1 NEW_LINE v . append ( i ) NEW_LINE DEDENT if ( S == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( S != 0 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT v1 = [ ] NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT it = i in v NEW_LINE if ( not it ) : NEW_LINE INDENT v1 . append ( i ) NEW_LINE DEDENT DEDENT j = 0 NEW_LINE f = 0 NEW_LINE for i in range ( 1 , L ) : NEW_LINE INDENT print ( v1 [ j ] , end = " ▁ " ) NEW_LINE j += 1 NEW_LINE DEDENT for i in range ( L , R + 1 ) : NEW_LINE INDENT print ( v [ f ] , end = " ▁ " ) NEW_LINE f += 1 NEW_LINE DEDENT for i in range ( R + 1 , N + 1 ) : NEW_LINE INDENT print ( v1 [ j ] , end = " ▁ " ) NEW_LINE j += 1 NEW_LINE DEDENT DEDENT return NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 6 NEW_LINE L = 3 NEW_LINE R = 5 NEW_LINE S = 8 NEW_LINE findPermutation ( N , L , R , S ) NEW_LINE DEDENT