Codeforces Round #168 (Div. 1), problem: (A) k-Multiple Free Set solution and Binary search version

Codeforces Round #168 (Div. 1), problem: (A) k-Multiple Free Set: http://codeforces.com/problemset/problem/274/A

Codeforces Round #168 (Div. 1), problem: (A) k-Multiple Free Set editorial: http://codeforces.com/blog/entry/6759

Codeforces Round #168 (Div. 1), problem: (A) k-Multiple Free Set solution: http://ideone.com/LlFWlA

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    int n, k, a[100005];
    map <int, int> m;
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    sort(a, a+n);
    for(int i=0; i<n; i++) {
        if(a[i]%k==0) {
            if(m.count(a[i]/k)==true) continue;
            else m.insert(make_pair(a[i], 0));
        }
        else m.insert(make_pair(a[i], 0));
    }
    printf("%d", m.size());
    return 0;
}

note: the problem is similar to UVa 11246 k-multiple set: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2203

you can also glance SE network for good mathy explanation: http://math.stackexchange.com/questions/662413/largest-k-multiple-free-set-out-of-a-fully-ordered-set

and here is BINARY SEARCH version: http://ideone.com/nNooz6

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int bin_src(int *arr, int j, int target) {
    int l=0, r=j-1, m;
    while(l<=r) {
        m=l+(r-l)/2;
        if(arr[m]==target) return 1;
        else if(arr[m]<target) l=m+1;
        else r=m-1;
    }
    return 0;
}

int main() {
    int n, k, a[100005], b[100005], j=0;
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    sort(a, a+n);
    for(int i=0; i<n; i++) if(a[i]%k!=0 || bin_src(b, j, a[i]/k)==0) b[j]=a[i], j++;
    printf("%d", j);
    return 0;
}

to learn about Binary Search sources:

1 - TopCoder: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

2 - Wikipedia: http://en.wikipedia.org/wiki/Binary_search_algorithm

3 - rosettacode: http://rosettacode.org/wiki/Binary_search#C

4 - stackoverflow: http://stackoverflow.com/questions/249392/binary-search-in-array

5 - http://algorithms.openmymind.net/search/binarysearch.html

6 - http://www.programmingsimplified.com/c/source-code/c-program-binary-search

and also look the below C code to understand better:

#include <stdio.h>
#include <stdlib.h>

int nextInt() {
    char ch;
    int sign, x;

    do {
        ch = getchar();
    } while (ch < '-');

    if (ch == '-') {
        sign = -1;
        ch = getchar();
    } else
        sign = 1;

    x = 0;
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return sign * x;
}

int compare(const void *a, const void *b) {
    return *(long long *)a - *(long long *)b;
}

int binarySearch(long long *data, int n, long long key) {
    int l = 0, r = n - 1, m;

    while (l <= r) {
        m = (l + r) / 2;

        if (key == data[m])
            return m;
        else if (key < data[m])
            r = m - 1;
        else
            l = m + 1;
    }

    return -1;
}

int flag[100000];

int main(void) {
    int i;
    int n, ans;
    long long k, a[100000];

    scanf("%d %lld", &n, &k);
    for (i = 0; i < n; i++)
        a[i] = nextInt();

    qsort(a, n, sizeof(long long), &compare);

    ans = 0;
    for (i = 0; i < n; i++)
        if (!flag[i]) {
            int tmp = binarySearch(a, n, a[i] * k);

            if (tmp != -1)
                flag[tmp] = 1;

            ans++;
        }

    printf("%d\n", ans);

    return 0;
}