aboutsummaryrefslogtreecommitdiff
path: root/2_keys_keyboard.c
blob: f3196e4ca0152b7d91211e74047157d2eef53a84 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 650. 2 Keys Keyboard
#include "leetcode.h"

/*
 * there is only one character 'A' on the screen of a notepad. you can perform
 * one of two operations on this notepad for each step. copy all characters
 * present on the screen (a partial copy is not allowed). paste the characters
 * which are copied last time. given an integer 'n', return the minimum number
 * of operations to get the character 'A' exactly 'n' times on the screen.
 */

int minSteps(int n) {
  const int primes[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
  if (n <= 5)
    return n == 1 ? 0 : n;
  for (int i = 0; i < 11; i++)
    if (!(n % primes[i]))
      return primes[i] + minSteps(n / primes[i]);
  return n;
}

int main() {
  printf("%d\n", minSteps(3)); // expect: 3
  printf("%d\n", minSteps(1)); // expect: 0
}