Skip to main content

Fill two instances of all numbers from 1 to n in a specific interval

The problem at hand involves filling two instances of all numbers from 1 to n in a specific interval. This means that you need to place two occurrences of each number within an interval of numbers, following certain conditions. The code provided seems to be a solution to this problem using a recursive approach.

Problem Statement and Description

Given a positive integer n, the problem is to arrange two instances of numbers from 1 to n in an array in such a way that the distance between two instances of the same number is equal to the value of the number itself. This arrangement should follow certain rules:

  1. Each number from 1 to n should be used exactly twice.
  2. The distance between two instances of the same number should be equal to the value of the number. For example, the distance between two instances of the number 3 should be 3.
  3. The numbers should be placed in the array in sequential order.

Example

Let's take an example with n = 4 to illustrate the problem:

For n = 4, the numbers are {1, 2, 3, 4}. We need to arrange two instances of these numbers in the array such that the conditions are met.

One possible arrangement is: 4 1 3 1 2 4 3 2

Here, the distance between two instances of 4 is 4, between two instances of 3 is 3, and so on.

Idea to Solve the Problem

The code you provided is an implementation of a recursive approach to solve this problem. The main idea is to use a backtracking strategy to try out different arrangements of the numbers and check if the conditions are met. If not, the algorithm backtracks and tries a different arrangement.

Code Solution

// C Program 
// Fill two instances of all numbers from 1 to n in a specific interval
#include <stdio.h>

//  Display calculated intervals
void display(int auxiliary[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf(" %d", auxiliary[i]);
	}
	printf("\n");
}
// Find the elements from 1 to n in specific intervals
int findInterval(int auxiliary[], int element, int size, int n)
{
	if (element > n)
	{
		return 1;
	}
	for (int i = 0; i < size; ++i)
	{
		if (auxiliary[i] == 0 && i + element + 1 < size && 
            auxiliary[i + element + 1] == 0)
		{
			// Insert element on particular distance
			auxiliary[i] = element;
			auxiliary[i + element + 1] = element;
			if (findInterval(auxiliary, element + 1, size, n))
			{
				return 1;
			}
			// Reset value
			auxiliary[i] = 0;
			auxiliary[i + element + 1] = 0;
		}
	}
	return 0;
}
// Handles the request of printing number intervals
void printInterval(int intervals)
{
	if (intervals <= 1)
	{
		return;
	}
	printf("Intervals size %d \n", intervals);
	// Used to store results
	int auxiliary[intervals *2];
	for (int i = 0; i < intervals *2; ++i)
	{
		auxiliary[i] = 0;
	}
	if (findInterval(auxiliary, 1, intervals *2, intervals) == 0)
	{
		printf("\n No result ");
	}
	else
	{
		// Display calculated result
		display(auxiliary, intervals *2);
	}
	printf("\n");
}
int main(int argc, char const *argv[])
{
	// Test case
	printInterval(4);
	printInterval(7);
	return 0;
}

Output

Intervals size 4
 4 1 3 1 2 4 3 2

Intervals size 7
 1 7 1 2 5 6 2 3 4 7 5 3 6 4

/*
    Java Program for
    Fill two instances of all numbers from 1 to n 
    in a specific interval.
*/
public class Interval
{
	//  Display calculated intervals
	public void display(int[] auxiliary, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + auxiliary[i]);
		}
		System.out.print("\n");
	}
	// Find the elements from 1 to n in specific intervals
	public boolean findInterval(int[] auxiliary, 
                                int element, int size, int n)
	{
		if (element > n)
		{
			return true;
		}
		for (int i = 0; i < size; ++i)
		{
			if (auxiliary[i] == 0 && i + element + 1 < size && 
                auxiliary[i + element + 1] == 0)
			{
				// Insert element on particular distance
				auxiliary[i] = element;
				auxiliary[i + element + 1] = element;
				if (findInterval(auxiliary, element + 1, size, n))
				{
					return true;
				}
				// Reset value
				auxiliary[i] = 0;
				auxiliary[i + element + 1] = 0;
			}
		}
		return false;
	}
	// Handles the request of printing number intervals
	public void printInterval(int intervals)
	{
		if (intervals <= 1)
		{
			return;
		}
		System.out.print("Intervals size " + intervals + " \n");
		// Used to store results
		int[] auxiliary = new int[intervals * 2];
		for (int i = 0; i < intervals * 2; ++i)
		{
			auxiliary[i] = 0;
		}
		if (findInterval(auxiliary, 1, intervals * 2, intervals) == false)
		{
			System.out.print("\n No result ");
		}
		else
		{
			// Display calculated result
			display(auxiliary, intervals * 2);
		}
		System.out.print("\n");
	}
	public static void main(String[] args)
	{
		Interval task = new Interval();
		// Test case
		task.printInterval(4);
		task.printInterval(7);
	}
}

Output

Intervals size 4
 4 1 3 1 2 4 3 2

Intervals size 7
 1 7 1 2 5 6 2 3 4 7 5 3 6 4

// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program for
    Fill two instances of all numbers from 1 to n 
    in a specific interval.
*/
class Interval
{
	public:
		//  Display calculated intervals
		void display(int auxiliary[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << " " << auxiliary[i];
			}
			cout << "\n";
		}
	// Find the elements from 1 to n in specific intervals
	bool findInterval(int auxiliary[], int element, int size, int n)
	{
		if (element > n)
		{
			return true;
		}
		for (int i = 0; i < size; ++i)
		{
			if (auxiliary[i] == 0 && i + element + 1 < size && 
                auxiliary[i + element + 1] == 0)
			{
				// Insert element on particular distance
				auxiliary[i] = element;
				auxiliary[i + element + 1] = element;
				if (this->findInterval(auxiliary, element + 1, size, n))
				{
					return true;
				}
				// Reset value
				auxiliary[i] = 0;
				auxiliary[i + element + 1] = 0;
			}
		}
		return false;
	}
	// Handles the request of printing number intervals
	void printInterval(int intervals)
	{
		if (intervals <= 1)
		{
			return;
		}
		cout << "Intervals size " << intervals << " \n";
		// Used to store results
		int auxiliary[intervals *2];
		for (int i = 0; i < intervals *2; ++i)
		{
			auxiliary[i] = 0;
		}
		if (this->findInterval(auxiliary, 1, intervals *2, intervals) == false)
		{
			cout << "\n No result ";
		}
		else
		{
			// Display calculated result
			this->display(auxiliary, intervals *2);
		}
		cout << "\n";
	}
};
int main()
{
	Interval *task = new Interval();
	// Test case
	task->printInterval(4);
	task->printInterval(7);
	return 0;
}

Output

Intervals size 4
 4 1 3 1 2 4 3 2

Intervals size 7
 1 7 1 2 5 6 2 3 4 7 5 3 6 4

// Include namespace system
using System;
/*
    Csharp Program for
    Fill two instances of all numbers from 1 to n 
    in a specific interval.
*/
public class Interval
{
	//  Display calculated intervals
	public void display(int[] auxiliary, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + auxiliary[i]);
		}
		Console.Write("\n");
	}
	// Find the elements from 1 to n in specific intervals
	public Boolean findInterval(int[] auxiliary, 
                                int element, int size, int n)
	{
		if (element > n)
		{
			return true;
		}
		for (int i = 0; i < size; ++i)
		{
			if (auxiliary[i] == 0 && i + element + 1 < size && 
                auxiliary[i + element + 1] == 0)
			{
				// Insert element on particular distance
				auxiliary[i] = element;
				auxiliary[i + element + 1] = element;
				if (this.findInterval(auxiliary, element + 1, size, n))
				{
					return true;
				}
				// Reset value
				auxiliary[i] = 0;
				auxiliary[i + element + 1] = 0;
			}
		}
		return false;
	}
	// Handles the request of printing number intervals
	public void printInterval(int intervals)
	{
		if (intervals <= 1)
		{
			return;
		}
		Console.Write("Intervals size " + intervals + " \n");
		// Used to store results
		int[] auxiliary = new int[intervals * 2];
		for (int i = 0; i < intervals * 2; ++i)
		{
			auxiliary[i] = 0;
		}
		if (this.findInterval(auxiliary, 1, 
                              intervals * 2, intervals) == false)
		{
			Console.Write("\n No result ");
		}
		else
		{
			// Display calculated result
			this.display(auxiliary, intervals * 2);
		}
		Console.Write("\n");
	}
	public static void Main(String[] args)
	{
		Interval task = new Interval();
		// Test case
		task.printInterval(4);
		task.printInterval(7);
	}
}

Output

Intervals size 4
 4 1 3 1 2 4 3 2

Intervals size 7
 1 7 1 2 5 6 2 3 4 7 5 3 6 4

package main
import "fmt"
/*
    Go Program for
    Fill two instances of all numbers from 1 to n 
    in a specific interval.
*/

//  Display calculated intervals
func display(auxiliary[] int, size int) {
	for i := 0 ; i < size ; i++ {
		fmt.Print(" ", auxiliary[i])
	}
	fmt.Print("\n")
}
// Find the elements from 1 to n in specific intervals
func findInterval(auxiliary[] int, element int, size int, n int) bool {
	if element > n {
		return true
	}
	for i := 0 ; i < size ; i++ {
		if auxiliary[i] == 0 && i + element + 1 < size && auxiliary[i + element + 1] == 0 {
			// Insert element on particular distance
			auxiliary[i] = element
			auxiliary[i + element + 1] = element
			if findInterval(auxiliary, element + 1, size, n) {
				return true
			}
			// Reset value
			auxiliary[i] = 0
			auxiliary[i + element + 1] = 0
		}
	}
	return false
}
// Handles the request of printing number intervals
func printInterval(intervals int) {
	if intervals <= 1 {
		return
	}
	fmt.Print("Intervals size ", intervals, " \n")
	// Used to store results
	var auxiliary = make([] int, intervals * 2)
	if findInterval(auxiliary, 1, intervals * 2, intervals) == false {
		fmt.Print("\n No result ")
	} else {
		// Display calculated result
		display(auxiliary, intervals * 2)
	}
	fmt.Print("\n")
}
func main() {
	
	// Test case
	printInterval(4)
	printInterval(7)
}

Output

Intervals size 4
 4 1 3 1 2 4 3 2

Intervals size 7
 1 7 1 2 5 6 2 3 4 7 5 3 6 4

<?php
/*
    Php Program for
    Fill two instances of all numbers from 1 to n 
    in a specific interval.
*/
class Interval
{
	//  Display calculated intervals
	public	function display($auxiliary, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo(" ".$auxiliary[$i]);
		}
		echo("\n");
	}
	// Find the elements from 1 to n in specific intervals
	public	function findInterval(&$auxiliary, $element, $size, $n)
	{
		if ($element > $n)
		{
			return true;
		}
		for ($i = 0; $i < $size; ++$i)
		{
			if ($auxiliary[$i] == 0 && $i + $element + 1 < $size &&
                $auxiliary[$i + $element + 1] == 0)
			{
				// Insert element on particular distance
				$auxiliary[$i] = $element;
				$auxiliary[$i + $element + 1] = $element;
				if ($this->findInterval($auxiliary, $element + 1, $size, $n))
				{
					return true;
				}
				// Reset value
				$auxiliary[$i] = 0;
				$auxiliary[$i + $element + 1] = 0;
			}
		}
		return false;
	}
	// Handles the request of printing number intervals
	public	function printInterval($intervals)
	{
		if ($intervals <= 1)
		{
			return;
		}
		echo("Intervals size ".$intervals." \n");
		// Used to store results
		$auxiliary = array_fill(0, $intervals * 2, 0);
		if ($this->findInterval(
          $auxiliary, 1, $intervals * 2, $intervals) == false)
		{
			echo("\n No result ");
		}
		else
		{
			// Display calculated result
			$this->display($auxiliary, $intervals * 2);
		}
		echo("\n");
	}
}

function main()
{
	$task = new Interval();
	// Test case
	$task->printInterval(4);
	$task->printInterval(7);
}
main();

Output

Intervals size 4
 4 1 3 1 2 4 3 2

Intervals size 7
 1 7 1 2 5 6 2 3 4 7 5 3 6 4

/*
    Node JS Program for
    Fill two instances of all numbers from 1 to n 
    in a specific interval.
*/
class Interval
{
	//  Display calculated intervals
	display(auxiliary, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + auxiliary[i]);
		}
		process.stdout.write("\n");
	}
	// Find the elements from 1 to n in specific intervals
	findInterval(auxiliary, element, size, n)
	{
		if (element > n)
		{
			return true;
		}
		for (var i = 0; i < size; ++i)
		{
			if (auxiliary[i] == 0 && i + element + 1 < size && 
                auxiliary[i + element + 1] == 0)
			{
				// Insert element on particular distance
				auxiliary[i] = element;
				auxiliary[i + element + 1] = element;
				if (this.findInterval(auxiliary, element + 1, size, n))
				{
					return true;
				}
				// Reset value
				auxiliary[i] = 0;
				auxiliary[i + element + 1] = 0;
			}
		}
		return false;
	}
	// Handles the request of printing number intervals
	printInterval(intervals)
	{
		if (intervals <= 1)
		{
			return;
		}
		process.stdout.write("Intervals size " + intervals + " \n");
		// Used to store results
		var auxiliary = Array(intervals * 2).fill(0);
		if (this.findInterval(auxiliary, 1, 
                              intervals * 2, intervals) == false)
		{
			process.stdout.write("\n No result ");
		}
		else
		{
			// Display calculated result
			this.display(auxiliary, intervals * 2);
		}
		process.stdout.write("\n");
	}
}

function main()
{
	var task = new Interval();
	// Test case
	task.printInterval(4);
	task.printInterval(7);
}
main();

Output

Intervals size 4
 4 1 3 1 2 4 3 2

Intervals size 7
 1 7 1 2 5 6 2 3 4 7 5 3 6 4

#    Python 3 Program for
#    Fill two instances of all numbers from 1 to n 
#    in a specific interval.
class Interval :
	#   Display calculated intervals
	def display(self, auxiliary, size) :
		i = 0
		while (i < size) :
			print(" ", auxiliary[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Find the elements from 1 to n in specific intervals
	def findInterval(self, auxiliary, element, size, n) :
		if (element > n) :
			return True
		
		i = 0
		while (i < size) :
			if (auxiliary[i] == 0 and 
                i + element + 1 < size and auxiliary[i + element + 1] == 0) :
				#  Insert element on particular distance
				auxiliary[i] = element
				auxiliary[i + element + 1] = element
				if (self.findInterval(auxiliary, element + 1, size, n)) :
					return True
				
				#  Reset value
				auxiliary[i] = 0
				auxiliary[i + element + 1] = 0
			
			i += 1
		
		return False
	
	#  Handles the request of printing number intervals
	def printInterval(self, intervals) :
		if (intervals <= 1) :
			return
		
		print("Intervals size ", intervals ," ")
		#  Used to store results
		auxiliary = [0] * (intervals * 2)
		if (self.findInterval(auxiliary, 1, 
                              intervals * 2, intervals) == False) :
			print("\n No result ", end = "")
		else :
			#  Display calculated result
			self.display(auxiliary, intervals * 2)
		
		print(end = "\n")
	

def main() :
	task = Interval()
	#  Test case
	task.printInterval(4)
	task.printInterval(7)

if __name__ == "__main__": main()

Output

Intervals size  4
  4  1  3  1  2  4  3  2

Intervals size  7
  1  7  1  2  5  6  2  3  4  7  5  3  6  4

#    Ruby Program for
#    Fill two instances of all numbers from 1 to n 
#    in a specific interval.
class Interval 
	#   Display calculated intervals
	def display(auxiliary, size) 
		i = 0
		while (i < size) 
			print(" ", auxiliary[i])
			i += 1
		end

		print("\n")
	end

	#  Find the elements from 1 to n in specific intervals
	def findInterval(auxiliary, element, size, n) 
		if (element > n) 
			return true
		end

		i = 0
		while (i < size) 
			if (auxiliary[i] == 0 && i + element + 1 < size && 
                auxiliary[i + element + 1] == 0) 
				#  Insert element on particular distance
				auxiliary[i] = element
				auxiliary[i + element + 1] = element
				if (self.findInterval(auxiliary, element + 1, size, n)) 
					return true
				end

				#  Reset value
				auxiliary[i] = 0
				auxiliary[i + element + 1] = 0
			end

			i += 1
		end

		return false
	end

	#  Handles the request of printing number intervals
	def printInterval(intervals) 
		if (intervals <= 1) 
			return
		end

		print("Intervals size ", intervals ," \n")
		#  Used to store results
		auxiliary = Array.new(intervals * 2) {0}
		if (self.findInterval(auxiliary, 1, 
                              intervals * 2, intervals) == false) 
			print("\n No result ")
		else
 
			#  Display calculated result
			self.display(auxiliary, intervals * 2)
		end

		print("\n")
	end

end

def main() 
	task = Interval.new()
	#  Test case
	task.printInterval(4)
	task.printInterval(7)
end

main()

Output

Intervals size 4 
 4 1 3 1 2 4 3 2

Intervals size 7 
 1 7 1 2 5 6 2 3 4 7 5 3 6 4


/*
    Scala Program for
    Fill two instances of all numbers from 1 to n 
    in a specific interval.
*/
class Interval()
{
	//  Display calculated intervals
	def display(auxiliary: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + auxiliary(i));
			i += 1;
		}
		print("\n");
	}
	// Find the elements from 1 to n in specific intervals
	def findInterval(auxiliary: Array[Int], 
      element: Int, size: Int, n: Int): Boolean = {
		if (element > n)
		{
			return true;
		}
		var i: Int = 0;
		while (i < size)
		{
			if (auxiliary(i) == 0 && i + element + 1 < size && 
                auxiliary(i + element + 1) == 0)
			{
				// Insert element on particular distance
				auxiliary(i) = element;
				auxiliary(i + element + 1) = element;
				if (findInterval(auxiliary, element + 1, size, n))
				{
					return true;
				}
				// Reset value
				auxiliary(i) = 0;
				auxiliary(i + element + 1) = 0;
			}
			i += 1;
		}
		return false;
	}
	// Handles the request of printing number intervals
	def printInterval(intervals: Int): Unit = {
		if (intervals <= 1)
		{
			return;
		}
		print("Intervals size " + intervals + " \n");
		// Used to store results
		var auxiliary: Array[Int] = Array.fill[Int](intervals * 2)(0);
		if (findInterval(auxiliary, 1, 
                         intervals * 2, intervals) == false)
		{
			print("\n No result ");
		}
		else
		{
			// Display calculated result
			display(auxiliary, intervals * 2);
		}
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Interval = new Interval();
		// Test case
		task.printInterval(4);
		task.printInterval(7);
	}
}

Output

Intervals size 4
 4 1 3 1 2 4 3 2

Intervals size 7
 1 7 1 2 5 6 2 3 4 7 5 3 6 4

/*
    Swift 4 Program for
    Fill two instances of all numbers from 1 to n 
    in a specific interval.
*/
class Interval
{
	//  Display calculated intervals
	func display(_ auxiliary: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", auxiliary[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Find the elements from 1 to n in specific intervals
	func findInterval(_ auxiliary: inout[Int], _ element: Int, 
      _ size: Int, _ n: Int) -> Bool
	{
		if (element > n)
		{
			return true;
		}
		var i: Int = 0;
		while (i < size)
		{
			if (auxiliary[i] == 0 && i + element + 1 < size && 
                auxiliary[i + element + 1] == 0)
			{
				// Insert element on particular distance
				auxiliary[i] = element;
				auxiliary[i + element + 1] = element;
				if (self.findInterval(&auxiliary, element + 1, size, n))
				{
					return true;
				}
				// Reset value
				auxiliary[i] = 0;
				auxiliary[i + element + 1] = 0;
			}
			i += 1;
		}
		return false;
	}
	// Handles the request of printing number intervals
	func printInterval(_ intervals: Int)
	{
		if (intervals <= 1)
		{
			return;
		}
		print("Intervals size ", intervals ," ");
		// Used to store results
		var auxiliary: [Int] = Array(repeating: 0, count: intervals * 2);
		if (self.findInterval(&auxiliary, 1, intervals * 2, intervals) == false)
		{
			print("\n No result ", terminator: "");
		}
		else
		{
			// Display calculated result
			self.display(auxiliary, intervals * 2);
		}
		print(terminator: "\n");
	}
}
func main()
{
	let task: Interval = Interval();
	// Test case
	task.printInterval(4);
	task.printInterval(7);
}
main();

Output

Intervals size  4
  4  1  3  1  2  4  3  2

Intervals size  7
  1  7  1  2  5  6  2  3  4  7  5  3  6  4

/*
    Kotlin Program for
    Fill two instances of all numbers from 1 to n 
    in a specific interval.
*/
class Interval
{
	//  Display calculated intervals
	fun display(auxiliary: Array < Int > , size: Int): Unit
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" " + auxiliary[i]);
			i += 1;
		}
		print("\n");
	}
	// Find the elements from 1 to n in specific intervals
	fun findInterval(auxiliary: Array < Int > , 
                     element: Int, size: Int, n: Int): Boolean
	{
		if (element > n)
		{
			return true;
		}
		var i: Int = 0;
		while (i < size)
		{
			if (auxiliary[i] == 0 && i + element + 1 < size && 
                auxiliary[i + element + 1] == 0)
			{
				// Insert element on particular distance
				auxiliary[i] = element;
				auxiliary[i + element + 1] = element;
				if (this.findInterval(auxiliary, element + 1, size, n))
				{
					return true;
				}
				// Reset value
				auxiliary[i] = 0;
				auxiliary[i + element + 1] = 0;
			}
			i += 1;
		}
		return false;
	}
	// Handles the request of printing number intervals
	fun printInterval(intervals: Int): Unit
	{
		if (intervals <= 1)
		{
			return;
		}
		print("Intervals size " + intervals + " \n");
		// Used to store results
		val auxiliary: Array < Int > = Array(intervals * 2)
		{
			0
		};
		if (this.findInterval(auxiliary, 1, 
                              intervals * 2, intervals) == false)
		{
			print("\n No result ");
		}
		else
		{
			// Display calculated result
			this.display(auxiliary, intervals * 2);
		}
		print("\n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Interval = Interval();
	// Test case
	task.printInterval(4);
	task.printInterval(7);
}

Output

Intervals size 4
 4 1 3 1 2 4 3 2

Intervals size 7
 1 7 1 2 5 6 2 3 4 7 5 3 6 4

Resultant Output Explanation

For the test cases given c code, here's the output:

  1. printInterval(4)

    The function is called with intervals = 4. The output represents the arrangement of numbers from 1 to 4 with two instances each, satisfying the conditions mentioned earlier. The output is: 4 1 3 1 2 4 3 2

  2. printInterval(7)

    The function is called with intervals = 7. Similarly, the output represents the arrangement of numbers from 1 to 7 with two instances each, satisfying the conditions: 1 7 1 2 5 6 2 3 4 7 5 3 6 4

Time Complexity

The time complexity of this approach is quite high because it involves a recursive backtracking strategy. In the worst case, each recursive call results in multiple branches of further recursive calls. The complexity can be approximated as O(2^n), where n is the value of 'intervals' mentioned to the 'printInterval' function. This complexity arises because at each level of recursion, you have two options (placing or not placing a number), leading to an exponential growth in the number of recursive calls.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment