Codility Lesson 12

12.1 - Chocolate By Numbers

Two positive integers N and M are given. Integer N represents the number of chocolates arranged in a circle, numbered from 0 to N − 1.

You start to eat the chocolates. After eating a chocolate you leave only a wrapper.

You begin with eating chocolate number 0. Then you omit the next M − 1 chocolates or wrappers on the circle, and eat the following one.

More precisely, if you ate chocolate number X, then you will next eat the chocolate with number (X + M) modulo N (remainder of division).

You stop eating when you encounter an empty wrapper.

For example, given integers N = 10 and M = 4. You will eat the following chocolates: 0, 4, 8, 2, 6.

The goal is to count the number of chocolates that you will eat, following the above rules.

Write a function:

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

that, given two positive integers N and M, returns the number of chocolates that you will eat.

For example, given integers N = 10 and M = 4. the function should return 5, as explained above.

Write an efficient algorithm for the following assumptions:

• N and M are integers within the range [1..1,000,000,000].

using System;

/**
 * 12.1 - Chocolate by Numbers
 * Paulo Santos
 * 27.Dec.2022
 */
class Solution {
    public int solution(int N, int M) {
        return (N / gdcModulo(N, M));
    }

    private int gdcModulo(int a, int b) {
        if (a % b == 0) return b;
        return gdcModulo(b, a % b);
    }
}

---

12.2 - Common Prime Divisors

A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.

A prime D is called a prime divisor of a positive integer P if there exists a positive integer K such that D * K = P. For example, 2 and 5 are prime divisors of 20.

You are given two positive integers N and M. The goal is to check whether the sets of prime divisors of integers N and M are exactly the same.

For example, given:

• N = 15 and M = 75, the prime divisors are the same: {3, 5};
• N = 10 and M = 30, the prime divisors aren't the same: {2, 5} is not equal to {2, 3, 5};
• N = 9 and M = 5, the prime divisors aren't the same: {3} is not equal to {5}.

Write a function:

class Solution 
{
  public int solution(int[] A, int[] B); 
}

that, given two non-empty arrays A and B of Z integers, returns the number of positions K for which the prime divisors of A[K] and B[K] are exactly the same.

For example, given:

    A[0] = 15   B[0] = 75
    A[1] = 10   B[1] = 30
    A[2] = 3    B[2] = 5

the function should return 1, because only one pair (15, 75) has the same set of prime divisors.

Write an efficient algorithm for the following assumptions:

• Z is an integer within the range [1..6,000];
• each element of arrays A and B is an integer within the range [1..2,147,483,647].

using System;

/**
 * 12.2 - Common Prime Divisors
 * Paulo Santos
 * 27.Dec.2022
 */
class Solution {
    public int solution(int[] A, int[] B) {

        var res = 0;
        for(var i = 0; i < A.Length; i++) {
            res += CheckDiv(A[i], B[i]);
        }
        return res;

    }

    private int CheckDiv(int a, int b) {
        if (a == b) return 1;

        var div = GDC(a, b);
        if (a == 1 || b == 1 || div == 1) return 0;

        while (a != 1) {
            var tstA = GDC(a, div);
            if (tstA == 1) break;
            a /= tstA;
        }
        if (a != 1) return 0;

        while (b != 1) {
            var tstB = GDC(b, div);
            if (tstB == 1) break;
            b /= tstB;
        }
        if (b != 1) return 0;

        return 1;
    }

    private int GDC(int a, int b) {
        if (a % b == 0) return b;
        return GDC(b, a % b);
    }
}