CODEWITHSUNDEEP
javarecursionreturn
Rahul
Rahul

Reputation: 331

Program seems to always return 1 for any input

I am attempting to solve this Competitive Programming Question called Thanos Sort. For some details on the question please click this link: https://codeforces.com/problemset/problem/1145/A This competition ended a very long time ago, so discussion is permitted. It seems to be a pretty straightforward question. I tried to solve the question using recursion (repetitively splitting the array in half and checking if it is sorted, and if I found that one of the halves was sorted, I return the value of the length of the half). Here is my code: 

import java.util.*;
import java.io.*;
class Main {
 public static void main(String[] args) throws IOException{
   BufferedReader b1 = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(b1.readLine());
   for(int i = 0; i<T; i++) {
     String vals [] = (b1.readLine()).split(" ");
     int nums [] = new int[vals.length];
     for(int j = 0; j<vals.length; j++) {
         nums[j] = Integer.parseInt(vals[j]);
     }
     System.out.println(solve(nums));
   }
 }
 public static int solve(int arr[]) {
   int temp1 [] = new int[arr.length/2];
   int temp2 [] = new int[arr.length/2];
   for(int i = 0; i<arr.length/2; i++) {
     temp1[i] = arr[i];
   }
   for(int i = arr.length/2; i<arr.length; i++) {
     temp2[i-(arr.length/2)] = arr[i];
   }
   if(isSorted(temp1) == true) {
     return temp1.length;
   }
    if(isSorted(temp2) == true) {
     return temp2.length;
   }
   solve(temp1);
   solve(temp2);
  return 1;
 } 
 public static boolean isSorted(int [] arr) {
   for(int i = 0; i<arr.length; i++) {
     if(arr.length == 1) {
       return true;
     }
     if(i < arr.length-2 && arr[i] < arr[i+1]) {
       continue;
     }
     else {
       return false;
     }
   }
   return true;
 }
}

My code seems to always output 1, when tested on any array. I understand that I have the "return 1" statement at the end of my code (I need to have this there since the other return statements are inside of if-statements). I believe that the error is being caused by the "return 1" statement I have. Any suggestions?

Upvotes: 0

Views: 45

Answers (1)

Elliott Frisch
Elliott Frisch

Reputation: 201447

When you recurse, you discard the value returned by the recursion. Change

solve(temp1);
solve(temp2);
return 1;

to something like

return Math.max(1, Math.max(solve(temp1), solve(temp2)));

Also, your isSorted algorithm appears to be broken. Iterate the array, check that each value is equal to or greater than the previous. Like,

public static boolean isSorted(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    return true;
}

Upvotes: 2

Related Questions