How do I solve this codility problem!!!

Question

1.00/5 (4 votes)

See more:

[^]

I have no idea how to solve this problem. Please can someone walk me through a simple solution because I'm a programming novice.

Thanks

Posted 27-Jan-16 23:52pm

Member 12292743

Add a Solution

Comments

Kornfeld Eliyahu Peter 28-Jan-16 6:00am

Have you event tried something?

3 solutions

Solution 2

Consider the binary representation of the number and count adjacent zeroes.
Hint: this could be a SHIFT and (bitwise) AND task.

Posted 28-Jan-16 0:13am

CPallini

Solution 1

You want to learn something. So it would be counterproductive to give you a solution. But I can give some hints:

Don't think 'decimal'. Just remember that values are already in their binary representation. So you can check single bits by applying a mask to the value.

It is obvious that checking all possible bits with corresponding masks would be inefficient. Isn't there an operation that can move bit wise?

The remaining tasks are just counting and determining a max. value.

Posted 28-Jan-16 0:07am

Jochen Arndt

Comments

Member 12292743 28-Jan-16 6:15am

How does one apply a mask to a value?

Jochen Arndt 28-Jan-16 6:22am

You did not told us what you may know already. So I had to assume that are at least some basics about logical operations. The operation is given in the next solution: AND.
To check for a single bit, this must be the only one set in the mask that is then ANDed with the value. The result can than be checked logically to determine if the bit is set or not using the NOT operator and/or comparing it with zero.

Member 12292743 28-Jan-16 7:43am

Okay so I read up on bit masking and it's starting to make sense.

Let's look at a simpler problem: how would I find the largest binary gap for one number?

I appreciate your help btw

Jochen Arndt 28-Jan-16 8:07am

What do you mean by one number?

The first task is to split the problem into parts having already in mind that it must be solved here using C language. For a binary zero gap this may be:

- Find the first 0 bit after a 1 bit (that is skip all 0 bits until a 1 bit occurs and then skip all 1 bits)
- When found, count the number of 0 bits until a 1 bit
- Now check if the count is larger than the max. count. If so set max. count.
- Repeat until all bits has been processed

Seeing the above you should recognize that using while loops may be a good idea, the first condition can be splitted into a setup part and a part executed for each gap detection, and there must be a break detection when there are no more 1 bits left:

- Setup: Skip 0 bits
- Process loop
- Skip 1 bits
- Break if there are no more 1 bits
- Count 0 bits
- Check if count greater than max. count
- Continue

The above can be now implemented in code. Here is a starting point
int solution(int N)
{
int count = 0;
int max_count = 0;
// Skip 0 bits
while (0 == (N & 1))
N >>= 1;
// Gap detection loop
while (N)
{
// Skip 1 bits
while (N & 1)
N >>= 1;
// To be done
}
return max_count;
}

Member 12292743 28-Jan-16 8:11am

One number as opposed to an array of numbers

Jochen Arndt 28-Jan-16 8:17am

Array?
There is no array involved in the assignment.

Member 12292743 28-Jan-16 8:19am

Oh my bad I was mixing up two problems.

Member 12292743 28-Jan-16 8:26am

What is the reason behind using the shift operator when skipping bits 'N>>=1'?

Jochen Arndt 28-Jan-16 8:34am

To be honest, you should try to find out yourself. It may be even better to start with a C tutorial razher than trying to solve assignments that are at this time beyond your skills.

The reason is simple:
You have a binary number and ANDing it with 1 checks if the lowest bit is set or not. When shifting right afterwards the next bit can be checked because that is then the lowest bit.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Andreas Gieriet · Accepted Answer · 2016-01-28T07:43:00

Solution 3

To tackle the problem systematically, you might employ a state machine.
E.g. you start by initializing the max_len and gap_len to 0, the State to Init and then process one bit after the other by following the states and actions as shown in this table:

Current State	Current Bit	Next State	Action
Init	0	Init	;
Init	1	Count	;
Count	0	Count	gap_len++;
Count	1	Count	max_len = max(max_len, gap_len); gap_len = 0;

Finally you return the resulting max_len value.
This is functional correct but maybe not optimal. E.g. max_len is updated even gap_len is zero, etc. But this is only relevant if speed is relevant. In such a case, more states might improve speed for the cost of complexity of the state machine. This is left as exercise, though. ;-)

Now, the state machine translates into something like this:

[EDIT] changed from define to enum [/EDIT]

C

...
enum { Init, Count } state = Init;
...
int n = ...
int max_len = 0;
int gap_len = 0;
for(int bit = 1; bit; bit<<=1) { // run as long as there is a moving bit in the mask
    int one = n & bit;
    switch(state) {
    case Init:
        // conditional state change
        if (one) {
            state = Count;
        }

        // no action
        break;
    case Count:
        // no state change

        // conditional action
        if (one) {
            if (max_len < gap_len) max_len = gap_len;
            gap_len = 0;
        } else {
            gap_len++;
        }
        break;
    default:
        assert(!"Unexpected State");
        break;
    }
}

Cheers
Andi

Posted 28-Jan-16 7:43am

Andreas Gieriet

Updated 28-Jan-16 16:08pm

v3

Comments

Member 12292743 28-Jan-16 13:51pm

Wow many thanks for your reply. I know other users aren't supposed to do my work for my nor did I expect them to do it, but I appreciate you going out of your way to do it. Thanks

Andreas Gieriet 28-Jan-16 13:53pm

If you learn something by example, I'm happy to help. Otherwise, it's a pity...
Cheers
Andi

[no name] 28-Jan-16 14:25pm

A 5 for this dedicated help.
Bruno

Andreas Gieriet 28-Jan-16 16:52pm

Thanks for your 5, Bruno!
Cheers
Andi

ridoy 28-Jan-16 14:43pm

my 5 too.

Andreas Gieriet 28-Jan-16 16:52pm

Thanks for your 5 too!
Cheers
Andi

Member 12292743 28-Jan-16 16:40pm

Don't use DEFINE when you don't have to. Use constants instead or better yet enumeration.

Andreas Gieriet 28-Jan-16 17:08pm

What do you mean by "hex"? If it's about the 0x80000000, then you need to learn about how to enter a numeric value in C. Internally, numbers are stored as bit patterns, e.g. for a 32-bit system an int as a 32 bit wide bit pattern. You can provide numeric integral values as decimal number (e.g. 1234, without leading zero = binary 00000000000000000000010011010010), as octal number (e.g. 01234, with leading zero and digits 0...7 = decimal 668 = binary 00000000000000000000001010011100), as hex number (e.g. 0x1234, with leading 0x or 0X and digits 0...9 and letters a...f and A...F, = decimal 4660 = binary 00000000000000000001001000110100). Unfortunately, you cannot enter the binary values, only decimal, octal and hex is supported.
Andi

Philippe Mori 28-Jan-16 22:01pm

I don't know what happened but when I edited my reply, a lot of editors opened with the same text and finally change were not even with my name.

Andreas Gieriet 28-Jan-16 22:04pm

Sure.
Cheers
Andi

Philippe Mori 28-Jan-16 21:56pm

Don't use DEFINE when you don't have to. You should use constants instead.

Andreas Gieriet 28-Jan-16 22:05pm

Yep. Agreed.
Cheers
Andi