Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

AVAILABLE EXERCISES:

Exercise 9

Bitwise operations (bit-ops)

Exercise 8

Frontend

Exercise 7

Data Structures

Exercise 6

SQL

Exercise 5

Coding skills

Exercise 4

Algorithmic skills

Exercise 3

2017 Contest

Exercise 2

2016 Contest

Exercise 1

2015 Contest

Decompose int into sum of ints having no consecutive 1s in binary form.

Spoken language:

A non-negative integer N is called *sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

Two non-negative integers P and Q are called a *sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

- 8 and 18 are a sparse decomposition of 26 (binary representation of 8 is "
1000", binary representation of 18 is "10010");- 9 and 17 are a sparse decomposition of 26 (binary representation of 9 is "
1001", binary representation of 17 is "10001");- 2 and 24 are not a sparse decomposition of 26; though 2 + 24 = 26, the binary representation of 24 is "
11000", which is not sparse.

Write a function:

int solution(int N);

that, given a non-negative integer N, returns any integer that is one part of a sparse decomposition of N. The function should return −1 if there is no sparse decomposition of N.

For example, given N = 26 the function may return 8, 9, 17 or 18, as explained in the example above. All other possible results for N = 26 are 5, 10, 16 and 21.

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A non-negative integer N is called *sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

Two non-negative integers P and Q are called a *sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

- 8 and 18 are a sparse decomposition of 26 (binary representation of 8 is "
1000", binary representation of 18 is "10010");- 9 and 17 are a sparse decomposition of 26 (binary representation of 9 is "
1001", binary representation of 17 is "10001");- 2 and 24 are not a sparse decomposition of 26; though 2 + 24 = 26, the binary representation of 24 is "
11000", which is not sparse.

Write a function:

int solution(int N);

that, given a non-negative integer N, returns any integer that is one part of a sparse decomposition of N. The function should return −1 if there is no sparse decomposition of N.

For example, given N = 26 the function may return 8, 9, 17 or 18, as explained in the example above. All other possible results for N = 26 are 5, 10, 16 and 21.

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A non-negative integer N is called *sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

Two non-negative integers P and Q are called a *sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

- 8 and 18 are a sparse decomposition of 26 (binary representation of 8 is "
1000", binary representation of 18 is "10010");- 9 and 17 are a sparse decomposition of 26 (binary representation of 9 is "
1001", binary representation of 17 is "10001");- 2 and 24 are not a sparse decomposition of 26; though 2 + 24 = 26, the binary representation of 24 is "
11000", which is not sparse.

Write a function:

class Solution { public int solution(int N); }

that, given a non-negative integer N, returns any integer that is one part of a sparse decomposition of N. The function should return −1 if there is no sparse decomposition of N.

For example, given N = 26 the function may return 8, 9, 17 or 18, as explained in the example above. All other possible results for N = 26 are 5, 10, 16 and 21.

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

func Solution(N int) int

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

class Solution { public int solution(int N); }

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

class Solution { public int solution(int N); }

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

function solution(N);

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

fun solution(N: Int): Int

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

function solution(N)

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

int solution(int N);

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

function solution(N: longint): longint;

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

function solution($N);

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

sub solution { my ($N)=@_; ... }

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

def solution(N)

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

def solution(n)

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

object Solution { def solution(n: Int): Int }

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

public func solution(_ N : Int) -> Int

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].

*sparse* if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "`101001`" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "`11010`" and it contains two consecutive 1s.

*sparse decomposition* of integer N if P and Q are sparse and N = P + Q.

For example:

1000", binary representation of 18 is "10010");1001", binary representation of 17 is "10001");11000", which is not sparse.

Write a function:

Private Function solution(N As Integer) As Integer

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [0..1,000,000,000].