-10

The cake is not a lie!

Commander Lambda has had an incredibly successful week: she completed the first test run of her LAMBCHOP doomsday device, she captured six key members of the Bunny Rebellion, and she beat her personal high score in Tetris. To celebrate, she's ordered cake for everyone - even the lowliest of minions! But competition among minions is fierce, and if you don't cut exactly equal slices of cake for everyone, you'll get in big trouble.

The cake is round, and decorated with M&Ms in a circle around the edge. But while the rest of the cake is uniform, the M&Ms are not: there are multiple colors, and every minion must get exactly the same sequence of M&Ms. Commander Lambda hates waste and will not tolerate any leftovers, so you also want to make sure you can serve the entire cake.

To help you best cut the cake, you have turned the sequence of colors of the M&Ms on the cake into a string: each possible letter (between a and z) corresponds to a unique color, and the sequence of M&Ms is given clockwise (the decorations form a circle around the outer edge of the cake).

Write a function called answer(s) that, given a non-empty string less than 200 characters in length describing the sequence of M&Ms, returns the maximum number of equal parts that can be cut from the cake without leaving any leftovers.

Languages

To provide a Python solution, edit solution.py
To provide a Java solution, edit solution.java

Test cases

Inputs:

(string) s = "abccbaabccba"

Output:

(int) 2

Inputs:

(string) s = "abcabcabcabc"

Output:

(int) 4

Anyone have idea on solving this? Here is my answer but failed for 6 test cases.

public class Answer {   
    public static int answer(String s) { 
        int split = 1;
        char c = s.charAt(0);
        for (int i = 1; i < s.length() - 1; i++) {
            if (c == s.charAt(i)) {
                if(s.charAt(i)!=s.charAt(i+1)){
                    split++;
                }
            }
        }
        return split;
    } 
}

enter image description here

12
  • Please share the code as text and not image.
    – Naman
    Jan 21, 2017 at 4:15
  • @nullpointer added Jan 21, 2017 at 4:20
  • Do you know the test cases you fail? What is the reasonning behind your solution? Maybe you should add it to the solution
    – user5156016
    Jan 21, 2017 at 4:22
  • Please add an explanation of what you did. You probably didn't analyze the problem well enough to take into account all possible scenarios. I have a working solution for you when you will update your question.
    – user5156016
    Jan 21, 2017 at 4:44
  • A brute force solution would be to first try to divide the cake into n slices of 1 character each. If they are not all equal (you can find this out very quickly) check if n is divisible by two, and if so, split the cake into slices 2 characters long, and check if they are equal, and so on, until you find a slice-length for which all slices are equal. Jan 21, 2017 at 5:13

12 Answers 12

2

I am not going to share the code right away since I guess Google uses Plagiarism checks on the codes. But I'll share the algorithm that I had used.

Algorithm:

loop from 1 to length of the string calculate if length/i is a whole number(because that's one of the possible answers) take the sub-string from index 0 to length/i count number of occurrences if number of occurrences equals length/i, check if you have a max value greater than length/i if yes make it as max

Pseudo-code:

max=1
loop i from (0 to length(string))
{
if length(array)%i equals 0
{
substring=array[0 TO length(array)/i)
number=count(substring in string)
}
if number==length(array)/i and number>max
max=number
}
return max

Complexity: O(M*K) where M is the length of string and K is the number of factors of length of the string.

Note: I don't exactly know how good/bad this algo is but it took very less time to execute all 10 test-cases.

1

I think this is a quick working not optimized solution. You basically suppose that you can have n parts. If it works you return, if not you suppose that you can have n-1 part and so one.

int result = -1;
    int len = s.length();
    for(int i = len; i > 0; i--){           
        int n = len/i;
        if( n * i == len){
            boolean valid = true;
            String part = s.substring(0,n);
            for(int j = 1; j < i; j++){

                if(!s.substring(j*n,j*n+n).equals(part)){
                    valid = false;
                    break;
                }

            }
            if(valid){
                result = i;
                break;
            }

        }


    }
4
  • As I said it is not optimized at all.
    – user5156016
    Jan 21, 2017 at 5:23
  • This is working all test cases passed! Great solution Jan 21, 2017 at 5:24
  • It is only a solution not a great one. But if you happen to know how to access that challenge site, please share.
    – user5156016
    Jan 21, 2017 at 5:25
  • 1
    It happens when search a lot of programming term, then will pop out something like this link shown. Google track on your browsing history based on what i google, cause i was enter this accidentally while researching some programming stuff. Jan 21, 2017 at 5:30
1

This is passing all the test cases.

def solution(s):

    length_of_str = len(s)

    for i in range(1,length_of_str+1):

        cmp_str = s[:i]

        count = s.count(cmp_str)

        if count*i == length_of_str:
            return count

print("Test case 1 : ")
print(solution("abccbaabccba"))

print("\nTest case 2 : ")
print(solution("abcabcabcabc"))
1
  • Similar - BUT - I added this code to the top : if (len_sequence) <= 0: print("No sequence was passed to the function") return 0 Also in order to see if we string fitted in correctly I used a find and replace - so if the sequence is not correct , then there would be some leftover charaters (below) : count_remainder= len(s.replace(s[:z],"")) if count_remainder ==0: return s.count(temp_lst_seq)
    – Daragh
    Mar 7, 2021 at 21:41
0

For a python based solution, this is what I could come up with, I know I could have used regex (findall) to get a better solution, and that the code could be further optimized. But this passed all the tests, and I was a bit lazy to optimize the solution further. Please comment if you have any cool suggestions

def sample(leng, split_list):
    for i in range(0, leng-1):

        if(split_list[i] == split_list[i+1]):
            if(i == leng-2):
                return leng
            else:
                continue
        else:
            return 1


def solution(s):
    # Your code here
    gem_str = s
    sample_num = 1
    str_length = len(gem_str)  # 12

    # gem_split_list = []

    for divider_value in range(1, str_length):
        split_list = []
        if(str_length % divider_value == 0):
            for x in range(0, str_length, divider_value):
                split_list.append(gem_str[x:x+divider_value])
            split_list_length = len(split_list)

            sample_num = sample(split_list_length, split_list)
            if(sample_num != 1):
                return sample_num
    return sample_num
0
def solution(s):

    length_of_str = len(s)

    for i in range(1,length_of_str):

        cmp_str = s[:i]

        count = s.count(cmp_str)

        if count*i == length_of_str:
            return count



print("Test case 1 : ")
print(solution("abccbaabccba"))

print("\nTest case 2 : ")
print(solution("abcabcabcabc"))
0

Here is a short and quick solution for python which has cleared all verification test,please comment and suggest if you have any cool idea.

def solution(s):
    length = len(exmp)  
    for x in range(1,length):
        if (length % x == 0):
            lis =[exmp[y:y+x] for y in range(0,length,x) ]   # for x in range(0,length,y): ;  lis.append(exmp[x:x+y])
            lis_len = len(lis)
            for z in range(0,lis_len-1):
                if (lis[z] == lis[z+1]): 
                    if (z==lis_len-2):
                        return lis_len
    return lis_len

#s= "abcabcabcabc" 
#s= "jaishreeramjaishreeramjaishreeram"
#s= "harekrishnaharekrishnaharekrishnaharekrishna"
solution(s)
0

My sol pass all the test cases and I believe it is O(N) speed.

def solution(s):
    n = len(s)
    if n<1:
        return 0
    # two pointers
    p1 = 0
    p2 = n-1
    seq1, seq2 = '', ''
    while p1<p2:
        seq1 = seq1+s[p1]
        seq2 = s[p2]+seq2
        if seq1 == seq2 and seq1 == s[p1+1:p1+len(seq1)+1]:
            return n/len(seq1)
        p1+=1
        p2-=1
    return 1

Even though it pass the test cases in foobar, but there is a type of corner case that this sol cannot pass, such as s='aabbaaaabbaa'.

solution with a few test cases in notebook.

0

This not the optimised one.. but passes all the test cases with O(n^2).

public class Solution {
 public static int solution(String s) {
    // Function calls are expensive, so to avoid calling length() multiple times
    int howLong = s.length();
    int count = 0;

    // Iterating through length of the input string from backwards
    for (int i = howLong; i > 0; i--) {
        int n = howLong / i;
        boolean flag = true;
        // Storing substring
        String subString = s.substring(0, n);

        // Check for substring repeated no. of times
        for (int j = 1; j < i; j++) {
            if (!s.substring(j * n, j * n + n).equals(subString)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            count = i;
            break;
        }
    }
    return count;
  }
}
0

Java recursive solution, passes all tests, including the edge case Ming mentioned. I added psvm so I can test ;)

public class App {
    public static void main(String[] args) throws Exception {
        System.out.println(solution("aabbaaaabbaa")); // one test case for example
    }
    public static int solution(String x) {
        int i = 1; // the smallest sequence we can have is 1 for example "aaaaaaaaaaa" would have the sequence of 1
        int sizeOfCake = x.length();
        while (i<=sizeOfCake/2){ // no need to go through all amounts of sequences because the smallest amount of pieces of cake is 2
            if(helpMethod(x.substring(i,sizeOfCake), x.substring(0,i))) {
                return sizeOfCake/i;
            }
            i++;
        }
        return 1; // You could argue that the whole cake is one peace so you are "cutting" 1 peace. If so it's probably going to Commander Lambda.
        // The tests only passed with 1 but I originally was going for: Math.round(Math.random())
    }
    
    static boolean helpMethod(String oneSliceLess, String sliceSequence) {
        int sizeOfSliceSequence = sliceSequence.length();
        int sizeOfOneSliceLess = oneSliceLess.length();
        if(sizeOfOneSliceLess >= sizeOfSliceSequence){
            return oneSliceLess.substring(0,sizeOfSliceSequence).equals(sliceSequence) &&
            helpMethod(oneSliceLess.substring(sizeOfSliceSequence,sizeOfOneSliceLess), sliceSequence);
        }
        return true;
    }
}
0

Try this?

public class Solution {
    public static int solution(String x) {
        if((x == null) || (x.length() == 0))
            return 0;

        int len = x.length();
        String targetString = x.toLowerCase();
        String pattern = "";
        for(int i = 0; i < len; i++) {
            String subString = targetString.substring(0, i);
            int len2 = targetString.replaceAll(subString, "").length();
            if(len2 == 0) {
                if ((pattern.length() == 0) || (subString.length() <= pattern.length()))
                    pattern = subString;
            }
        }

        if (pattern.length() == 0) {
            return 1;
        }

        return len / pattern.length();
    }
}
0

I did this test 3 months ago, wrote this solution in Python that passes every test:

import re
    
def solution(s):
    seq = re.search('^(.+?)\\1*$', s).group(1)
    return len(s) / len(seq)
0

Solution

def solution(s):
    if s:
        n = len(s)
        if n < 200:
            count = 0
            for length in range(1, n//2 + 1):
                if n % length == 0:
                    substring = s[:length]
                    repeats = n // length
                    if substring * repeats == s:
                        # consider only max no. of parts
                        if count < repeats:
                            count = repeats
            if count == 0:
                # if all parts are unique
                if len(s) == len(set(s)):
                    return 1
            return count

Still, I passed 7 out of 10 test cases, failed 3 hidden test cases.

Share optimized solution

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.