Write function that, given an integer number N, returns array of integers 1..N arranged in a way, so sum of each 2 consecutive numbers is a square.
Solution is valid if and only if following two criterias are met:
Each number in range 1..N is used once and only once.
Sum of each 2 consecutive numbers is a perfect square(root square).
the result is a list of 1-n numbers in a specific order according to the rules above!!!
Example For N=15 solution could look like this:
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]
check-
16 16 16 16 16 16 16
/+\ /+\ /+\ /+\ /+\ /+\ /+\
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]
\+/ \+/ \+/ \+/ \+/ \+/ \+/
9 25 9 25 9 25 9
9 = 3*3
16 = 4*4
25 = 5*5
length of the returned list is n=15 and uses numbers from 1-n(15)
If there is no solution, return null For example if N=5, then numbers 1,2,3,4,5 cannot be put into square sums row: 1+3=4, 4+5=9, but 2 has no pairs and cannot link [1,3] and [4,5].
solution list return must be using numbers up to n and the length must be equal to n
my solution is using recursive method, here is my attempts:
import java.util.*;
public class SquareSums {
public static List<Integer> gg= new ArrayList<Integer>() ;
public static List<Integer> buildUpTo(int n) {
int checkCurrent=1,firstInList=1;
while(checkCurrent<=n+1){
boolean[] flag= new boolean[n+1];
List<Integer> l= new ArrayList<Integer>();
l=checker(n,checkCurrent,l,1,flag,firstInList, true);//n, prev, list, current, flag
checkCurrent++;
if(l.size()==n) {System.out.println("true "+ n);return l;}
}
return null;
}
public static List<Integer> checker(int num, int current,List<Integer> l,int prev, boolean[] flag,int k, boolean one){
if(l.size()==num) {return l;}
else if(prev>num+1 || current>num) {return l;}
if(one) {
flag[current]=true;
l.add(current);print(l);
l=checker(num,1,l,current,flag,1,false);
}
flag[prev]=true;
System.out.println("check if square root: "+" num1: "+prev+ " num2: "+current+" sum is: "+(prev+current)+" sqrt: "+Math.sqrt(prev+current)+ " sqrt int: "+Math.floor(Math.sqrt(prev+current)));
if(current<flag.length &&!flag[current] && Math.sqrt(prev+current)==Math.floor(Math.sqrt(prev+current))) {
l.add(current);print(l);
l=checker(num,1,l,current,flag,1,false);
}
else {
print(l);
l=checker(num,k++,l,prev,flag,k,false);
}
return l;
}
public static void main(String[] args) {
List<Integer> l= buildUpTo(15);
print(l);
}
static void print(List<Integer> l) {
System.out.println(" -------------------- ");
for(int i=0;i<l.size();i++) {
System.out.println(l.get(i));
}
System.out.println(" --------------------- ");
System.out.println(" ");
System.out.println(" ");
}
}
although I get true it fails because of the following:
how can I solve/fix the code in order for It to work properly(using a recursive method&no streams?)?
here is the testing code:
import org.junit.Test;
import org.junit.runners.JUnit4;
import java.util.List;
public class Tests {
@Test
public void sampleTests() {
List.of(5,15,16,23,37).forEach(Check::isGood);
}
}
EDIT:
then with the help of the code solution posted down below I edited my code a bit to this but it still doesn't work as it should.
public class SquareSums {
public static List<Integer> gg= new ArrayList<Integer>() ;
public static List<Integer> buildUpTo(int n) {
int checkCurrent=1;
while(checkCurrent<=n+1){
List<Integer> l=checker(n,checkCurrent,new ArrayList<Integer>(),1,new boolean[n+1],1);//n, prev, list, current, flag
checkCurrent++;
if(l.size()==n) {System.out.println("true "+ n);return l;}
}
return gg;
}
static boolean checkPerfectSquare(double x)
{
double sq = Math.sqrt(x);
return ((sq - Math.floor(sq)) == 0);
}
public static List<Integer> checker(int num, int current,List<Integer> l,int prev, boolean[] flag,int k){
if(l.size()==num) {return l;}
else if(prev>num+1 || current>num) {return l;}
if(l.size()==0) {
flag[current]=true;
l.add(current);System.out.println(l);
l=checker(num,1,l,current,flag,1);
}
flag[prev]=true;
if(current<flag.length &&!flag[current] && checkPerfectSquare(prev+current)) {
l.add(current);System.out.println(l);
l=checker(num,1,l,current,flag,1);
l.remove(l.size()-1);
flag[l.size()-1]=false;
}
else {
System.out.println(l);
l=checker(num,k++,l,prev,flag,k);
}
return l;
}
public static void main(String[] args) {
List<Integer> l= buildUpTo(15);
System.out.println("\n"+"Answer is: ");
System.out.println(" -------------------- ");
System.out.println(l);
System.out.println(" -------------------- ");
}
}
i ran through the code and when I run it on example n=15 which is true, its suppose to return a list which starts with 9, on mine on the debugger/printing on 9 it prints
[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, **1, 8**]
and the expected actual result is:(not my code, the real solution when n=15)
[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, **6, 10, 15, 1, 8**]
if we look closely we can see where my code went wrong. it seems that i need to add something to the recursion which goes back to try every option. how can i do so?