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 | C ++ program for the above approach ; 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 B without y ; Stores the set C with ( 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPossible ( multiset < int > A , multiset < int > B , set < int > C , int N ) { if ( A . size ( ) == 0 || B . size ( ) == 0 ) { if ( C . size ( ) == N ) { return true ; } else { return false ; } } bool ans = false ; for ( auto x : A ) { for ( auto y : B ) { multiset < int > _A = A ; _A . erase ( _A . find ( x ) ) ; multiset < int > _B = B ; _B . erase ( _B . find ( y ) ) ; set < int > _C = C ; _C . insert ( ( x + y ) % N ) ; ans = ( ans || isPossible ( _A , _B , _C , N ) ) ; } } return ans ; } void rearrangeArray ( int arr [ ] , int N , int K ) { multiset < int > A ; for ( int i = 0 ; i < N ; i ++ ) { A . insert ( arr [ i ] % N ) ; } multiset < int > B ; for ( int i = 0 ; i < N ; i ++ ) { B . insert ( ( i * K ) % N ) ; } set < int > C ; if ( isPossible ( A , B , C , N ) ) { cout << " YES " ; } else { cout << " NO " ; } } int main ( ) { int arr [ ] = { 1 , 2 , 0 } ; int K = 5 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; rearrangeArray ( arr , N , K ) ; return 0 ; }