Member Avatar for kanugula

Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
Petya has a number consisting of n digits without leading zeroes. He represented it as an array of digits without leading zeroes. Let's call it d. The numeration starts with 1, starting from the most significant digit. Petya wants to perform the following operation k times: find the minimum x (1 ≤ x < n) such that dx = 4 and dx + 1 = 7, if x is odd, then to assign dx = dx + 1 = 4, otherwise to assign dx = dx + 1 = 7. Note that if no x was found, then the operation counts as completed and the array doesn't change at all.
You are given the initial number as an array of digits and the number k. Help Petya find the result of completing k operations.

Input
The first line contains two integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 109) — the number of digits in the number and the number of completed operations. The second line contains n digits without spaces representing the array of digits d, starting with d1. It is guaranteed that the first digit of the number does not equal zero.
Output
In the single line print the result without spaces — the number after the k operations are fulfilled.

Examples input
7 4
4727447

output
4427477

input
4 2
4478

output
4478

Note In the first sample the number changes in the following
sequence: 4727447 → 4427447 → 4427477 → 4427447 → 4427477. In the second sample: 4478 → 4778 → 4478.

2 4 5 7 9

output
YES

  • 3 Contributors
  • 2 Replies
  • 410 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by kasraneni2003

Dani AI

Generated

Short expert note and a compact C reference (requested by ). 's reminder to show work is noted — the explanation below highlights the key idea and the one tricky case; the code that follows is a direct, safe C implementation of the standard solution for Codeforces 122D (Lucky Transformation). Codeforces 122D. (codeforces.com)

Core idea (brief): scan the string left-to-right once and apply the rule at the first found "47". Using 0-based indices: if the pair is at index i (s[i]=='4' && s[i+1]=='7') then

  • if i is even (1-based position odd) set s[i+1] = '4';
  • else set s[i] = '7'.
    Most changes only affect later positions, so one linear pass suffices. The single tricky case is a local pattern "447" where a toggle between two adjacent positions can occur; detect it when i is odd and s[i-1]=='4' and resolve by using the parity of remaining k (no further full simulation is needed). This yields an O(n) solution. A worked explanation with the same observation is available here. (blog.nowcoder.net)
#include <stdio.h>
#include <string.h>
#include <stdint.h>

int main(void) {
    int n;
    long long k;
    char s[100005];
    if (scanf("%d %lld", &n, &k) != 2) return 0;
    if (scanf("%s", s) != 1) return 0;
    int len = (int)strlen(s);

    for (int i = 0; i + 1 < len && k > 0; ++i) {
        if (s[i] == '4' && s[i+1] == '7') {
            if ((i % 2) == 0) {          /* 0-based even => 1-based odd */
                s[i+1] = '4';
                --k;
            } else {                     /* 0-based odd => 1-based even */
                if (i > 0 && s[i-1] == '4') {
                    if (k % 2 == 1) s[i] = '7';
                    k = 0;               /* cycle consumed; finish */
                    break;
                } else {
                    s[i] = '7';
                    --k;
                }
            }
        }
    }

    printf("%s\n", s);
    return 0;
}

Notes: compile with a standard C compiler (for example gcc -std=c99 -O2 -o lucky lucky.c). Time is O(n) and memory O(n). Care must be taken with parity: reading the string into a 0-based C array means index parity is the inverse of the problem's 1-based parity.

Recommended Answers

All 2 Replies

Member Avatar for rproffitt

From https://www.daniweb.com/welcome/rules
"Do provide evidence of having done some work yourself if posting questions from school or work assignments"

Unless this is you asking for quotes on how much, then state that so folk know you are hiring out.

Member Avatar for kasraneni2003

can i get c code for this

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.