Encrypt a Secret Code with Two Key Values: C++ and Python

Bob’s secret-code problem reduces to one formula: compute S^N mod 10, raise that single digit to M, then reduce the result by 10^9+7.

The challenge is that S can be up to 10^9 and both N and M can reach 10^10. Computing S^N directly is not feasible at those sizes. Two mathematical observations make the problem tractable: last digits of powers follow short repeating cycles, and binary exponentiation computes large modular powers in O(log exponent) steps.

This article derives the algorithm from first principles, provides corrected C++ and Python implementations, and traces three examples by hand to verify the output before running any code.

The Encryption Formula

The full formula is Encrypted Code = ((S^N mod 10)^M) mod 1000000007.

Breaking it into three stages makes the logic clear:

• Stage 1: Reduce S to its last digit. Powers modulo 10 depend only on the last digit of the base, so S^N mod 10 = (S % 10)^N mod 10. For S = 237, you only need to work with the digit 7.
• Stage 2: Find the last digit of (S % 10)^N. This is the mathematically interesting step. The digit 7 raised to increasing powers cycles through 7, 9, 3, 1, 7, 9, 3, 1, … indefinitely. Knowing the cycle length (4 for digit 7) and the value of N mod 4 gives the answer without computing the full power.
• Stage 3: Take the result X from Stage 2 and compute X^M mod 1000000007 using binary exponentiation. X is now a single digit (0 to 9), making the computation fast.

Last-Digit Cycles in Integer Powers

Every digit from 0 to 9 has a finite cycle when raised to successive powers. The table below lists the cycle and its length for each digit.

Last digit of S	Cycle of d^1, d^2, d^3, ...	Cycle length
0	0	1
1	1	1
2	2, 4, 8, 6	4
3	3, 9, 7, 1	4
4	4, 6	2
5	5	1
6	6	1
7	7, 9, 3, 1	4
8	8, 4, 2, 6	4
9	9, 1	2

The maximum cycle length is 4. Digits 0, 1, 5, and 6 are trivial: their last digit never changes regardless of the exponent.

To find which element of the cycle d^N lands on, the index is (N - 1) % cycle_length. For N = 1 (the first power) the index is 0, giving the first element of the cycle. For N = 5 with a cycle of length 4, the index is (5-1) % 4 = 0, which correctly maps back to the first element (same last digit as d^1).

This index formula differs from an alternative that appears in several published solutions: (N % cycle_length) - 1. When N is an exact multiple of the cycle length, that formula produces index -1. Python silently handles -1 as the last element of a list and gives the correct answer by coincidence. C++ accessing a vector at index -1 is undefined behavior and can produce incorrect results or crashes. The (N-1) % cycle_length formula avoids both issues.

Step-by-Step Algorithm

Given S, N, and M:

• Step 1: Compute last_digit = S % 10.
• Step 2: Look up the cycle for last_digit from the table above. Get cycle_length.
• Step 3: Compute idx = (N - 1) % cycle_length. Look up X = cycle[idx].
• Step 4: Compute encrypted = binary_exp(X, M, 1000000007), where binary_exp(base, exp, mod) returns base^exp mod mod using the fast doubling method.

The binary exponentiation in Step 4 works by repeatedly squaring the base and reducing by the modulus:

• If exp is odd, multiply result by the current base, reduce by mod.
• Square the base, reduce by mod.
• Halve the exponent (integer division).
• Repeat until exp reaches 0.

This gives O(log M) multiplications instead of O(M). For M = 10^10, that is roughly 33 iterations instead of ten billion.

C++ Implementation

The corrected implementation uses the (N-1) % cycle_length index formula throughout.

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;

// Binary exponentiation: computes base^exp mod mod in O(log exp)
long long binary_exp(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) result = result * base % mod;
        base = base * base % mod;
        exp /= 2;
    }
    return result;
}

long long encrypt(long long S, long long N, long long M) {
    int last = (int)(S % 10);

    // Last-digit cycle table indexed by digit 0-9
    vector<vector<int>> cycles = {
        {0}, {1}, {2, 4, 8, 6}, {3, 9, 7, 1}, {4, 6},
        {5}, {6}, {7, 9, 3, 1}, {8, 4, 2, 6}, {9, 1}
    };

    const vector<int>& cycle = cycles[last];
    int cycle_len = (int)cycle.size();

    // (N-1) % cycle_len: correct for all N >= 1, no negative-index risk
    int idx = (int)((N - 1) % cycle_len);
    long long X = cycle[idx];

    return binary_exp(X, M, MOD);
}

int main() {
    long long S, N, M;
    cin >> S >> N >> M;
    cout << encrypt(S, N, M) << "\n";
    return 0;
}

A few implementation notes worth stating for placement-test contexts:

• base %= mod at the start of binary_exp prevents intermediate products from overflowing a long long before the first reduction.
• The (int)((N - 1) % cycle_len) cast is safe because cycle_len is at most 4, so the result fits in an int with no truncation.
• The function returns 0 correctly when X = 0 (i.e., when S is a multiple of 10), because 0^M mod anything = 0 and binary_exp initialises result = 1, then the first multiplication 1 * 0 % MOD = 0 gives the right answer.

For additional C++ patterns used in coding-test contexts, see how to find the smallest and largest element in an array.

Python Implementation

Python’s arbitrary-precision integers mean there is no overflow risk, but binary exponentiation is still the right approach for large M, since Python’s built-in pow(base, exp, mod) performs it internally.

def binary_exp(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            result = result * base % mod
        base = base * base % mod
        exp //= 2
    return result

def encrypt(S, N, M):
    last = S % 10

    cycles = {
        0: [0], 1: [1], 2: [2, 4, 8, 6], 3: [3, 9, 7, 1], 4: [4, 6],
        5: [5], 6: [6], 7: [7, 9, 3, 1], 8: [8, 4, 2, 6], 9: [9, 1]
    }

    cycle = cycles[last]
    cycle_len = len(cycle)

    idx = (N - 1) % cycle_len    # always 0 to cycle_len-1 for N >= 1
    X = cycle[idx]

    return binary_exp(X, M, 1000000007)

S, N, M = map(int, input().split())
print(encrypt(S, N, M))

Python’s pow(X, M, 1000000007) is a shorter alternative to the explicit loop; both give the same result. The explicit binary_exp function above is included to make the algorithm visible, which is what placement interviewers expect when asking you to walk through your solution.

Worked Examples and the Bug That Breaks C++

Three examples traced by hand, each verifying that the computed X matches the true last digit of S^N.

Example 1: S = 2, N = 3, M = 4

• last = 2 % 10 = 2; cycle = [2, 4, 8, 6]; cycle_len = 4
• idx = (3-1) % 4 = 2; X = 8
• Check: 2^3 = 8, last digit = 8. Correct.
• encrypted = binary_exp(8, 4, 10^9+7) = 8^4 = 4096 mod 10^9+7 = 4096

Example 2: S = 37, N = 6, M = 3

• last = 37 % 10 = 7; cycle = [7, 9, 3, 1]; cycle_len = 4
• idx = (6-1) % 4 = 5 % 4 = 1; X = 9
• Check: 7^6 = 117649, last digit = 9. Correct.
• encrypted = binary_exp(9, 3, 10^9+7) = 9^3 = 729 mod 10^9+7 = 729

Example 3 (bug-trigger case): S = 12, N = 4, M = 2

• last = 12 % 10 = 2; cycle = [2, 4, 8, 6]; cycle_len = 4
• Correct index: idx = (4-1) % 4 = 3; X = 6
• Check: 12^4 = 20736, last digit = 6. Correct.
• encrypted = binary_exp(6, 2, 10^9+7) = 36 mod 10^9+7 = 36
• Buggy formula: (4 % 4) - 1 = -1. Python: cycle[-1] = 6 (correct by accident). C++ vector: index -1 is undefined behavior (likely wrong value or crash).

Example 3 is the case that silently produces a wrong answer in C++ with the published formula. N = 4 is a multiple of the cycle length 4, so the subtraction produces -1. The corrected (N-1) % cycle_length formula produces index 3, which is the last element of the four-element cycle — the same element Python accidentally selects. The difference is that (N-1) % cycle_length is well-defined and predictable in every language.

For a broader set of coding patterns that appear in placement tests, see data structures interview questions.

The binary exponentiation pattern in Step 4 appears outside placement tests too. Fast matrix exponentiation used in sequence models, hashing functions in LLM token embeddings, and big-integer arithmetic in privacy-preserving ML all use the same “halve the exponent, square the base” loop. TinkerLLM at ₹299 starts from coding exercises like this and builds toward applying those primitives inside real LLM pipelines, connecting competitive-programming foundations to deployed AI systems.