Tutorialspoint.dev

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.

Examples:

Input: n = 3
Output: res[] = {3, 1, 2, 1, 3, 2}

Input: n = 2
Output: Not Possible

Input: n = 4
Output: res[] = {4, 1, 3, 1, 2, 4, 3, 2}

We strongly recommend to minimize the browser and try this yourself first.

One solution is to Backtracking. The idea is simple, 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. Following is implementation of the idea.

C

// A backtracking based C Program to fill two instances of all numbers 
// from 1 to n in a specific way
#include <stdio.h>
#include <stdbool.h>
  
// 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++)
     {
        // 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;
        }
     }
     return false;
}
  
// This function prints the result for input number 'n' using fillUtil()
void fill(int n)
{
    // 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;
  
    // If solution is possible, then print it.
    if (fillUtil(res, n, n))
    {
        for (i=0; i<2*n; i++)
           printf("%d ", res[i]);
    }
    else
        puts("Not Possible");
}
  
// Driver program
int main()
{
  fill(7);
  return 0;
}

Python3

# A backtracking based Python3 Program
# to fill two instances of all numbers
# from 1 to n in a specific way
def fillUtil(res, curr, n):
      
    # 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. 
  
    # 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
    for i in range(2 * n - curr - 1):
  
        # Two 'curr' should be placed
        # at 'curr+1' distance
        if res[i] == 0 and res[i + curr + 1] == 0:
  
            # Place 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] = 0
            res[i + curr + 1] = 0
  
    return False
  
def fill(n):
      
    # This function prints the result
    # for input number 'n' using fillUtil()
  
    # Create an array of size 2n and
    # initialize all elements in it as 0
    res = [0] * (2 * n)
  
    # If solution is possible, then print it.
    if fillUtil(res, n, n):
        for i in range(2 * n):
            print(res[i], end = ' ')
        print()
    else:
        print("Not Possible")
  
# Driver Code
if __name__ == '__main__':
    fill(7)
  
# This code is contributed by vibhu4agarwal


Output:

7 3 6 2 5 3 2 4 7 6 5 1 4 1

The above solution may not be the best possible solution. There seems to be a pattern in the output. I an Looking for a better solution from other geeks.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter