Check if elements of given array can be rearranged such that ( arr [ i ] + i * K ) % N = i for all values of i in range [ 0 , N | Function to check if it is possible to generate all numbers in range [ 0 , N - 1 ] using the sum of elements + in the multiset A and B mod N ; If no more pair of elements can be selected ; If the number of elements in C = N , then return true ; Otherwise return false ; Stores the value of final answer ; Iterate through all the pairs in the given multiset A and B ; Stores the set A without x ; Stores the set A without y ; Stores the set A without x + y % N ; Recursive call ; Return Answer ; Function to check if it is possible to rearrange array elements such that ( arr [ i ] + i * K ) % N = i ; Stores the values of arr [ ] modulo N ; Stores all the values of i * K modulo N ; Print Answer ; Driver code
def isPossible ( A , B , C , N ) : NEW_LINE INDENT if ( len ( A ) == 0 or len ( B ) == 0 ) : NEW_LINE INDENT if ( len ( C ) == N ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT ans = False NEW_LINE for x in A : NEW_LINE INDENT for y in B : NEW_LINE INDENT _A = A NEW_LINE _A . remove ( x ) NEW_LINE _B = B NEW_LINE _B . remove ( y ) NEW_LINE _C = C NEW_LINE _C . add ( ( x + y ) % N ) NEW_LINE ans = ( ans or isPossible ( _A , _B , _C , N ) ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def rearrangeArray ( arr , N , K ) : NEW_LINE INDENT A = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT A . append ( arr [ i ] % N ) NEW_LINE DEDENT A . sort ( ) NEW_LINE B = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT B . append ( ( i * K ) % N ) NEW_LINE DEDENT B . sort ( ) NEW_LINE C = set ( ) NEW_LINE if isPossible ( A , B , C , N ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT arr = [ 1 , 2 , 0 ] NEW_LINE K = 5 NEW_LINE N = len ( arr ) NEW_LINE rearrangeArray ( arr , N , K ) NEW_LINE