Fill two instances of all numbers from 1 to n in a specific way - GeeksforGeeks
Fill two instances of all numbers from 1 to n in a specific way Given a number n, create an array of size 2n such that the array contains 2 instances of every number from 1 to n, and the number of elements between two instances of a number i is equal to i. If such a configuration is not possible, then print the same.
we place two instances of n at a place, then recur for n-1. If recurrence is successful, we return true, else we backtrack and try placing n at different location.
curr element can be placed i and i+curr+1,
Read full article from Fill two instances of all numbers from 1 to n in a specific way - GeeksforGeeks
Fill two instances of all numbers from 1 to n in a specific way Given a number n, create an array of size 2n such that the array contains 2 instances of every number from 1 to n, and the number of elements between two instances of a number i is equal to i. If such a configuration is not possible, then print the same.
Input: n = 3
Output: res[] = {3, 1, 2, 1, 3, 2}
there are 3 elements between 3 and 3, 2 elements between 2, etc.we place two instances of n at a place, then recur for n-1. If recurrence is successful, we return true, else we backtrack and try placing n at different location.
curr element can be placed i and i+curr+1,
// A recursive utility function to fill two instances of numbers from // 1 to n in res[0..2n-1]. 'curr' is current value of n.bool fillUtil(int res[], int curr, int n){ // If current number becomes 0, then all numbers are filled if (curr == 0) return true; // Try placing two instances of 'curr' at all possible locations // till solution is found int i; for (i=0; i<2*n-curr-1; i++) // i+curr+1 < 2n { // Two 'curr' should be placed at 'curr+1' distance if (res[i] == 0 && res[i + curr + 1] == 0) { // Plave two instances of 'curr' res[i] = res[i + curr + 1] = curr; // Recur to check if the above placement leads to a solution if (fillUtil(res, curr-1, n)) return true; // If solution is not possible, then backtrack res[i] = res[i + curr + 1] = 0; //is this needed? seems no useful, as we always set i value. } } return false;} // Create an array of size 2n and initialize all elements in it as 0 int res[2*n], i; for (i=0; i<2*n; i++) res[i] = 0;