Solved

countX

Posted on 2016-09-09
22
70 Views
Last Modified: 2016-09-14
Hi,

I am working on below challenge
http://codingbat.com/prob/p170371

Given a string, compute recursively (no loops) the number of lowercase 'x' chars in the string.

countX("xxhixx") → 4
countX("xhixhix") → 3
countX("hi") → 0
i was not clear on how to find the number of x using recursion? please advise
0
Comment
Question by:gudii9
  • 14
  • 6
  • 2
22 Comments
 
LVL 11

Expert Comment

by:tel2
ID: 41792066
Do you know what recursion is?
If so, tell us what you know about recursion, and we might be able to make sure your understanding is correct.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41792181
http://introcs.cs.princeton.edu/java/23recursion/

The idea of calling one function from another immediately suggests the possibility of a function calling itself. The function-call mechanism in Java supports this possibility, which is known as recursion.
Your first recursive program. The "Hello, World" for recursion is the factorial function, which is defined for positive integers n by the equation
n!=n×(n−1)×(n−2)×…×2×1
n!=n×(n−1)×(n−2)×…×2×1
The quantity n! is easy to compute with a for loop, but an even easier method in Factorial.java is to use the following recursive function:
public static long factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n-1);
}
We can trace this computation in precisely the same way that we trace any sequence of function calls.
factorial(5)
   factorial(4)
      factorial(3)
         factorial(2)
            factorial(1)
               return 1
            return 2*1 = 2
         return 3*2 = 6
      return 4*6 = 24
   return 5*24 = 120

reading from above link as above.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41792183
how to get base case for this challenge?
how to draw diagram like below all the way till base case

factorial(5)
   factorial(4)
      factorial(3)
         factorial(2)
            factorial(1)
               return 1
            return 2*1 = 2
         return 3*2 = 6
      return 4*6 = 24
   return 5*24 = 120
0
 
LVL 27

Expert Comment

by:rrz
ID: 41793087
This challenge is the same programming  problem as
https://www.experts-exchange.com/questions/28968901/countHi-challenge.html  
how to get base case for this challenge?
The base case is
When you found all the "x"s  return 0.
You can use a String method to search for x.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41793539
Return 1  or return 0?
0
 
LVL 11

Assisted Solution

by:tel2
tel2 earned 250 total points
ID: 41793567
In the case of factorials, you'll return 1 (or alternatively return n when n == 1).  If you returned 0, then 0 would be multiplied by the other numbers which would always result in 0, but that's not how factorials work, so use 1.  When the other numbers are multiplied by 1 the result will not be changed, which is good.

In the case of counting, return 0 (or alternatively return n when n == 0).  0 will be added to the other numbers, which will not change the result, which is good.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41793633
sure. let me try
0
 
LVL 27

Expert Comment

by:rrz
ID: 41793768
how to draw diagram like below all the way till base case
I couldn't do it that way. Here is what I wrote.
public class Fact{
	public static void main(String[] args){
	    System.out.println(" factorial(5) equals " + factorial(5));
	}
	public static int factorial(int n) {
	    System.out.println(" factorial(" + n + ")");
		if(n==1){
			System.out.println(" return 1");
			return 1;
		}
		System.out.println(" return " + n + " * factorial(" + (n-1) + ")");
        return n * factorial(n-1);
    }
}

Open in new window

My output:
 factorial(5)
 return 5 * factorial(4)
 factorial(4)
 return 4 * factorial(3)
 factorial(3)
 return 3 * factorial(2)
 factorial(2)
 return 2 * factorial(1)
 factorial(1)
 return 1
 factorial(5) equals 120
0
 
LVL 7

Author Comment

by:gudii9
ID: 41796709
package com.solution;

import java.io.*;

public class CountX {
	public static void main(String args[]) {
		String Str = new String("xxhixx");

		System.out.print("Return Value :");
		System.out.println(Str.substring(1));
		/*
		 * System.out.print("Return Value :" );
		 * System.out.println(Str.substring(10, 15) );
		 */
		System.out.println(countX("value is" + countX("xxhixx")));
	}

	public static int countX(String str) {
	    if (str.length() == 0){ 
	    	return 0;
	    		};
	    if (str.charAt(0) == 'x') {
	    	return 1 + countX(str.substring(1));
	    	};
	    	else {
		   return countX(str.substring(1));}
	
}
}

Open in new window


above gives below error at line 25

Syntax error on token "else", delete this token

please advise
0
 
LVL 7

Author Comment

by:gudii9
ID: 41796867
package com.solution;

import java.io.*;

public class Count8 {
	public static void main(String args[]) {
		String Str = new String("xxhixx");

		System.out.print("Return Value :");
		System.out.println(Str.substring(1));
		/*
		 * System.out.print("Return Value :" );
		 * System.out.println(Str.substring(10, 15) );
		 */
		System.out.println("value is" + count8(8818));
	}

	public static int count8(int n) {
		//public int count8(int n) {
			  if (n < 1) return 0;
			  if (n % 10 == 8 && (n / 10) % 10 == 8) return 2 + count8(n/10);
			  else if (n % 10 == 8) return 1 + count8(n/10);
			  else return count8(n/10);
			}
	}
		 /* else {
		  return count8(n/10);
		  }*/
		   /* if(n % 10 == 8){
				if(next digit is 8)return 2 + count8(n / 10);
				else return 1 + count8(n / 10);*/
		    

Open in new window

public int countX(String str) {
   
	    if (str.length() == 0){ 
	    	return 0;
	    		};
	    if (str.charAt(0) == 'x') {
	    	return 1 + countX(str.substring(1));
	    	};
	    	else {
		   return countX(str.substring(1));
	    	  
	    	}
	    	
	    	return 1;
	
}

Open in new window

i see i made a stupid mistake of putting ; next to } of if block above passed all tests
0
 
LVL 7

Author Comment

by:gudii9
ID: 41796877
public int countX(String str) {
   
	    if (str.length() == 0){ 
	    	return 0;
	    		};
	    if (str.charAt(0) == 'x') {
	    	return 1 + countX(str.substring(1));
	    	}
	    	else {
		   return countX(str.substring(1));
	    	  
	    	}
	    	
	    //	return 1;
	
}

Open in new window


i wonder why same code in eclipse gives wrong result

package com.solution;

import java.io.*;

public class CountX {
	public static void main(String args[]) {
		String Str = new String("xxhixx");

		System.out.print("Return Value :");
		System.out.println(Str.substring(1));
		/*
		 * System.out.print("Return Value :" );
		 * System.out.println(Str.substring(10, 15) );
		 */
		System.out.println(countX("value is" + countX("xxhixx")));
	}

	public static int countX(String str) {
		if (str.length() == 0) {
			return 0;
		}
		if (str.charAt(0) == 'x') {
			return 1 + countX(str.substring(1));
		} else {
			//else {
				return countX(str.substring(1));
			//}
		}

		// return 1;

		/*
		 * if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
		 * return 1 + countX(str.substring(1)); }; else { return
		 * countX(str.substring(1));
		 * 
		 * }
		 * 
		 * return 1;
		 */

		/*
		 * public int countX(String str) {
		 * 
		 * if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
		 * return 1 + countX(str.substring(1)); } else { return
		 * countX(str.substring(1));
		 * 
		 * }
		 */

		// return 1;

	}

}

Open in new window

Return Value :xhixx
0
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 27

Expert Comment

by:rrz
ID: 41796927
Your logic in your method was fine.  It works like the following.
import java.io.*;
public class X {
	public static void main(String args[]) {
		String inputStr = new String("xxhixx");
		System.out.println(" value is " + countX(inputStr));
	}
	public static int countX(String str) {
	    if (str.length() == 0){ 
	    	return 0;
	    		}
	    if (str.charAt(0) == 'x') {
	    	return 1 + countX(str.substring(1));
	    	}
	    	else {
		   return countX(str.substring(1));}
	
	}
}

Open in new window

0
 
LVL 27

Accepted Solution

by:
rrz earned 250 total points
ID: 41796932
My solution was a little different.
public int countX(String str) {
  int index = str.indexOf("x");
  if(index == -1) return 0;
  else return 1 + countX(str.substring(index + 1));
}

Open in new window

0
 
LVL 7

Author Comment

by:gudii9
ID: 41796945
package com.solution;

import java.io.*;

public class CountX {
	public static void main(String args[]) {
		String Str = new String("xxhixx");

		// System.out.print("Return Value :");
		// System.out.println(Str.substring(1));
		/*
		 * System.out.print("Return Value :" );
		 * System.out.println(Str.substring(10, 15) );
		 */
		System.out.println(countX("value is" + countX("xxhixx")));
	}

	public static int countX(String str) {
		if (str.length() == 0) {
			return 0;
		}
		if (str.charAt(0) == 'x') {
			return 1 + countX(str.substring(1));
		} else {
			// else {
			return countX(str.substring(1));
			// }
		}

		// return 1;

		/*
		 * if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
		 * return 1 + countX(str.substring(1)); }; else { return
		 * countX(str.substring(1));
		 * 
		 * }
		 * 
		 * return 1;
		 */

		/*
		 * public int countX(String str) {
		 * 
		 * if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
		 * return 1 + countX(str.substring(1)); } else { return
		 * countX(str.substring(1));
		 * 
		 * }
		 */

		// return 1;

	}

}

Open in new window


what is difference between above not working code and below working coe
package com.solution;

import java.io.*;

public class CountX2 {
	public static void main(String args[]) {
		String inputStr = new String("xxhixx");
		System.out.println(" value is " + countX(inputStr));
	}

	public static int countX(String str) {
		if (str.length() == 0) {
			return 0;
		}
		if (str.charAt(0) == 'x') {
			return 1 + countX(str.substring(1));
		}

		else {
			return countX(str.substring(1));
		}

	}
}

Open in new window


eclipse also aligned it differently with else block. I used beyondcompare for text comparison but could not notice any difference to my eyes?
compare.png
0
 
LVL 27

Expert Comment

by:rrz
ID: 41796964
		System.out.println(countX("value is" + countX("xxhixx")));

Open in new window

That is wrong. It should be
System.out.println(" value is " + countX(inputStr));

Open in new window

0
 
LVL 7

Author Comment

by:gudii9
ID: 41798247
           System.out.println(countX("value is" + countX("xxhixx")));

Select all
 
Open in new window
That is wrong. It should be
System.out.println(" value is " + countX(inputStr));

i could not catch even after using beyondcompare. how to make my eyes, brain as sharp as yours?
what is the difference of passing inputStr or passign directly value of inputStr which is xxhixx

To me both seems one and the same?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41798270
package com.solution;

import java.io.*;

public class CountX {
	public static void main(String args[]) {
		String Str = new String("xxhixx");

		// System.out.print("Return Value :");
		// System.out.println(Str.substring(1));
		/*
		 * System.out.print("Return Value :" );
		 * System.out.println(Str.substring(10, 15) );
		 */
		System.out.println(countX("value is" + countX(Str)));
	}

	public static int countX(String str) {
		if (str.length() == 0) {
			return 0;
		}
		if (str.charAt(0) == 'x') {
			return 1 + countX(str.substring(1));
		} else {
			// else {
			return countX(str.substring(1));
			// }
		}

		// return 1;

		/*
		 * if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
		 * return 1 + countX(str.substring(1)); }; else { return
		 * countX(str.substring(1));
		 * 
		 * }
		 * 
		 * return 1;
		 */

		/*
		 * public int countX(String str) {
		 * 
		 * if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
		 * return 1 + countX(str.substring(1)); } else { return
		 * countX(str.substring(1));
		 * 
		 * }
		 */

		// return 1;

	}

}

Open in new window


above also gives 0?
0
 
LVL 27

Expert Comment

by:rrz
ID: 41798364
how to make my eyes, brain as sharp as yours?
We(coders) have all been there. Sometimes we can't see something right in front on our faces. One time I spent 4 hours looking for a error that was just a simple capitalization mistake. I can't explain it. It is just a occupational hazard.  
what is the difference of passing inputStr or passign directly value of inputStr which is xxhixx

 To me both seems one and the same?
It is the same.
above also gives 0?
You still have
System.out.println(countX("value is" + countX(Str)));

Open in new window

Where you should have
System.out.println("value is" + countX(Str));

Open in new window

0
 
LVL 7

Author Comment

by:gudii9
ID: 41798378
You still have
System.out.println(countX("value is" + countX(Str)));

Select all
 
Open in new window
Where you should have
System.out.println("value is" + countX(Str));

i used countX two times
0
 
LVL 7

Author Comment

by:gudii9
ID: 41798380
occupational hazard.  
like this word
0
 
LVL 7

Author Comment

by:gudii9
ID: 41798382
package com.solution;

import java.io.*;

public class CountX {
	public static void main(String args[]) {
		String Str = new String("xxhixx");

		// System.out.print("Return Value :");
		// System.out.println(Str.substring(1));
		/*
		 * System.out.print("Return Value :" );
		 * System.out.println(Str.substring(10, 15) );
		 */
		System.out.println("value is" + countX(Str));
	}

	public static int countX(String str) {
		if (str.length() == 0) {
			return 0;
		}
		if (str.charAt(0) == 'x') {
			return 1 + countX(str.substring(1));
		} else {
			// else {
			return countX(str.substring(1));
			// }
		}

		// return 1;

		/*
		 * if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
		 * return 1 + countX(str.substring(1)); }; else { return
		 * countX(str.substring(1));
		 * 
		 * }
		 * 
		 * return 1;
		 */

		/*
		 * public int countX(String str) {
		 * 
		 * if (str.length() == 0){ return 0; }; if (str.charAt(0) == 'x') {
		 * return 1 + countX(str.substring(1)); } else { return
		 * countX(str.substring(1));
		 * 
		 * }
		 */

		// return 1;

	}

}

Open in new window


above finally works
0
 
LVL 7

Author Comment

by:gudii9
ID: 41798392
gives below output
value is4
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

746 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now