Home > Software design >  Every k-th digit cyclic problem using strings in C
Every k-th digit cyclic problem using strings in C

Time:10-04

Given some number in a form of string, I want to extract every k-th number from it. Then I go through the remaining string and extract every k-th number again. The thing I get as a result should be the number formed by these extracted ones(in a proper order). Example: 123456789, k = 3 --> 369485271

My algorithm is as follows: While the lenght of the string allows extracting every k-th number, I go through the string and store every k-th element in another string. Then I delete the extracted elements from the original string by tracking the proper index of an element and proceed forvard while the lenght of my str is sufficient. I can't figure out what's the problem with my code. And maybe my approach isn't that good and there are some better/simpler ways of diong this?

#include <stdio.h>
#include <string.h>
void remove(char *str, unsigned int index) {
    char *src;
    for (src = str index; *src != '\0'; *src = *(src 1),  src) ;
    *src = '\0';
}
int main() {
    char number[100];
    char result[100];
    int k;
    printf("Enter a string: ");
    scanf("%s",number);
    printf("Enter a key: ");
    scanf("%d",&k);
    while (strlen(number)>k-1) {
        for (int i = 0, p = 0; number[i] != '\0'; i  ) {
            if (i % k == (k-1)) {
                result[p] = number[i];
                p  ;
            }
        }
        for (int j = 0; number[j] != '\0'; j  ){
            if (j % k == (k-1)) {
                remove(number, j);
                j =1;  /*since the index was shifted due to removing an element*/
            }
        }
    }
puts(result);
return 0;
}

CodePudding user response:

The following code seems to be what you want:

void remove_(char *str, unsigned int index) {
    char *src;
    for (src = str index; *src != '\0'; *src = *(src 1),  src) ;
    *src = '\0';
}
int main() {
    char number[100];
    char result[100];
    int tmp[100];
    int tp = 0;
    int k;
    printf("Enter a string: ");
    scanf("%s",number);
    printf("Enter a key: ");
    scanf("%d",&k);
    int p = 0;
    while (strlen(number)>k-1) {
        for (int i = 0; number[i] != '\0'; i  ) {
            printf("i: %d,k: %d\n",i,k);
            if (i % k == (k-1)) {
                result[p  ] = number[i];
                printf("number[i]: %c\n", number[i]);
            }
            
        }
        printf("%s\n",number);
        for (int j = 0; number[j] != '\0'; j  ){
            if (j % k == (k-1)) {
                tmp[tp  ] = j;
                printf("j: %d,k: %d\n",j,k);
                printf("%c\n",number[j]);
//                remove_(number, j);
//                j =1;  /*since the index was shifted due to removing an element*/
            }
        }
        for (; tp; --tp) {
            remove_(number, tmp[tp-1]);
        }
//        for (int j = 0; number[j] != '\0'; j  ){
//            if (j % k == (k-1)) {
//                printf("j: %d,k: %d\n",j,k);
//                printf("%c\n",number[j]);
//                remove_(number, j);
//                j-=1;  /*since the index was shifted due to removing an element*/
//            }
//        }
        tp=0;
        printf("%s\n",number);
        printf("===================\n");
    }
    result[p] = number[0];
    puts(result);
    return 0;
}

You can try to output your code commented by me, and you will naturally understand the problem. The most important thing is that every while loop, you need to remove the elements in number at once.

By the way, your algorithm is similar to the Josephus problem, but your solution is not the best. Then you can continue to research and reduce its complexity.

CodePudding user response:

You some issues:

  • You start writing your output from scratch again in each iteration of your while loop.
  • You do not handle the last digits
  • You do not treat the input as a cyclic input.
  • You do not terminate your output string.
  • remove is already a name of standard library function.

A shorter version could be this (untested):

#include <stdio.h>
#include <string.h>
void remove_digit(char *str, unsigned int index) {
    char *src;
    for (src = str index; *src != '\0'; *src = *(src 1),  src)
        ;
}
int main() {
    char number[100];
    char result[100];
    int k;
    printf("Enter a string: ");
    scanf("%s",number);
    printf("Enter a key: ");
    scanf("%d",&k);
    int p = 0;
    int i = 0;
    int skip = k-1; // We remove 1 digit and skip k-1 digits
    while (number[0] != 0) {
        i = (i   skip) % strlen(number);
        result[p] = number[i];
        p  ;
        remove_digit(number, i);
    }
    number[p] = 0;
    puts(result);
    return 0;
}
  • Related