Order of indices which is lexicographically smallest and sum of elements is <= X | C # implementation of the approach ; Function to return the chosen indices ; Maximum indices chosen ; Try to replace the first element in ans by i , making the order lexicographically smaller ; If no further replacement possible return ; If found an index smaller than ind and sum not exceeding X then remove index of smallest value from ans and then add index i to ans ; Driver code ; Print the chosen indices
using System ; using System . Collections . Generic ; class GFG { static List < int > solve ( int X , List < int > A ) { int min = int . MaxValue ; int ind = - 1 ; for ( int i = 0 ; i < A . Count ; i ++ ) { if ( A [ i ] < min ) { min = A [ i ] ; ind = i ; } } int maxIndChosen = X / min ; List < int > ans = new List < int > ( ) ; if ( maxIndChosen == 0 ) { return ans ; } for ( int i = 0 ; i < maxIndChosen ; i ++ ) { ans . Add ( ind ) ; } int temp = maxIndChosen ; int sum = maxIndChosen * A [ ind ] ; for ( int i = 0 ; i < ind ; i ++ ) { if ( sum - X == 0 temp == 0 ) break ; while ( ( sum - A [ ind ] + A [ i ] ) <= X && temp != 0 ) { ans . RemoveAt ( 0 ) ; ans . Add ( i ) ; temp -- ; sum += ( A [ i ] - A [ ind ] ) ; } } ans . Sort ( ) ; return ans ; } public static void Main ( String [ ] args ) { int [ ] arr = { 5 , 6 , 4 , 8 } ; List < int > A = new List < int > ( arr ) ; int X = 18 ; List < int > ans = solve ( X , A ) ; for ( int i = 0 ; i < ans . Count ; i ++ ) Console . Write ( ans [ i ] + " ▁ " ) ; } }