Examples of nth sequence


  • 117
    X

    At the beginning, I got confusions about what is the nth sequence. Well, my solution is accepted now, so I'm going to give some examples of nth sequence here. The following are sequence from n=1 to n=10:

     1.     1
     2.     11
     3.     21
     4.     1211
     5.     111221 
     6.     312211
     7.     13112221
     8.     1113213211
     9.     31131211131221
     10.   13211311123113112211
    

    From the examples you can see, the (i+1)th sequence is the "count and say" of the ith sequence!

    Hope this helps!


  • 0
    M

    You may want to edit this so that the numbers are easier to read. Just stick them in the code example.


  • 0
    L

    I had the same confusion. Thank you for sharing.


  • 4
    L

    Careercup has a same problem, I think its description is better:
    http://www.careercup.com/question?id=4425679

    "Count and Say problem" Write a code to do following:

    n String to print
    0 1
    1 1 1
    2 2 1
    3 1 2 1 1
    ...
    Base case: n = 0 print "1"
    for n = 1, look at previous string and write number of times a digit is seen and the digit itself. In this case,

    digit 1 is seen 1 time in a row... so print "1 1"

    for n = 2, digit 1 is seen two times in a row, so print "2 1"

    for n = 3, digit 2 is seen 1 time and then digit 1 is seen 1 so print "1 2 1 1"

    for n = 4 you will print "1 1 1 2 2 1"

    Consider the numbers as integers for simplicity. e.g. if previous string is "10 1" then the next will be "1 10 1 1" and the next one will be "1 1 1 10 2 1"


  • 0
    Q

    this is really helpful. I think more than 5 min and see some solution, but get no idea about what the problem is trying to tell. Your explain is very clear. thanks~


  • 12

    Here is a slick answer:

    public class Solution {
        public String countAndSay(int n) {
            if(n <= 0) return "-1";
            String result = "1";
            
            for(int i = 1; i < n; i ++) {
                result = build(result);
            }
            return result;
        }
        
        private String build(String result) {
            StringBuilder builder = new StringBuilder();
            int p = 0;
            while(p < result.length()) {
                char val = result.charAt(p);
                int count = 0;
                
                while(p < result.length() && 
                  result.charAt(p) == val){
                    p ++;
                    count ++;
                }
                builder.append(String.valueOf(count));
                builder.append(val);
            }
            return builder.toString();
        }
    }

  • 0
    J

    It's really helpful. The question is really misleading. I couldn't figure out if n=6 what the sequence will be. You help me out of it. Thx.


  • 0
    X

    Thanks. The question mislead me


  • 0
    A

    @yavinci I love this slick solution. Spot on!


  • -1
    R
    This post is deleted!

  • 0
    R

    @rainny2 That's two for loops.


  • 0

    @xin15 Thanks! I have included your example in the Hints section. I have also updated the description and provided few examples to avoid confusion. Hopefully this helps. :)


  • 0

    If we have more than 9 '1' in sequence, like 11 '1's ("11111111111"), how should we say that?


  • 0
    M

    @RunRunCode You would say 11 1, but it is not something that can get generated from 1. Nothing above 3 can be, since you’d need to have two combiners of the same number next to each other.


  • 0

    @mike3

    Thanks. I found out it's true that there won't be any number larger than 3. But this question sounds legitimate (maybe essential) for us to clarify the requirements before actually writing code.

    I'm curious how a real interviewer would answer this question since it's inappropriate for him/her to either say

    1. I don't think about that, (He/She should know the requirements well enough to ask a question)
    2. or there won't be any number bigger than 3. (This sounds like giving some hints. We need to design the algorithm and run it to understand the requirements?)

  • 0
    A

    @yavinci said in Examples of nth sequence:

    public String countAndSay(int n) {
    if(n <= 0) return "-1";
    String result = "1";

        for(int i = 1; i < n; i ++) {
            result = build(result);
        }
        return result;
    }
    
    private String build(String result) {
        StringBuilder builder = new StringBuilder();
        int p = 0;
        while(p < result.length()) {
            char val = result.charAt(p);
            int count = 0;
            
            while(p < result.length() && 
              result.charAt(p) == val){
                p ++;
                count ++;
            }
            builder.append(String.valueOf(count));
            builder.append(val);
        }
        return builder.toString();
    }
    

    Awesome..


  • 0
    P

    @xin15 That helps. God count and say


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.