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:
- Each number from 1 to n should be used exactly twice.
- 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.
- 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:
-
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
-
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.
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