Fedor and New Game · Interview Problem

Back to problems

Codeforces

Easy

Bit Manipulation

Arrays

Math

Fedor and New Game

Count how many existing numbers differ from a given number in at most $k$ bit positions.

Acceptance 0%

Start Practice

Problem Statement

Problem

You are given an integer $n$ and a limit $k$ . Then you are given $n$ integers representing numbers already in the game, and one special integer $f$ representing Fedor's number.

For every given number, compare its binary representation with $f$ . A number is considered compatible if the two numbers differ in at most $k$ bit positions. Your task is to count how many of the $n$ numbers are compatible with $f$ .

In other words, for each number $a_i$ , compute the number of set positions where the bits of $a_i$ and $f$ are different, and count it if that value is at most $k$ .

Input Format

The first line contains three integers $n$ , $m$ , and $k$ .
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ .
The third line contains one integer $f$ .

Output Format

Print a single integer: the number of values among $a_1, a_2, \dots, a_n$ that differ from $f$ in at most $k$ bit positions.

Constraints

$1 \le n \le 1000$
$1 \le m \le 10$
$0 \le k \le m$
$0 \le a_i, f < 2^m$

Examples

Sample cases returned by the problem API.

Example 1

Input

3 4 1
1 2 3
2

Output

Explanation

Compare each value with 2:

1 differs in 2 bit positions
2 differs in 0 bit positions
3 differs in 1 bit position So the answer is 2.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress