Programming Problems 1

Any doubts or clarifications regarding the solution to these problems can be posted in comments.

1. Unlucky Numbers

There are few numbers considered to be unlucky(It contains only 4 and 7. ). Our goal is to find count of such numbers in the range of positive integers a and b.
For Example:
Input:: a = 10 b = 20
Output:: 0

Input:: a = 30 b = 50
Output:: 2 (44, 47)

2. Ideal String
An ideal string is a string where the 1-based index of the first occurrence of each letter is equal to the number of occurrences of that letter in the string. For example, the “BAOOOA” is an ideal string (quotes for clarity only). The letter ‘B’ appears 1 time, and its index is 1. The letter ‘A’ occurs 2 times and its first index is 2. The letter ‘O’ occurs 3 times and its first index is 3.

Given an int length, return the lexicographical smallest ideal string of that length containing only uppercase letters (‘A’-‘Z’). If there are no such ideal strings of that length, return an empty String instead.

PS: A possibly optimal solution to this problem has been provided here. Do post any comments/issues/improvements to it in the comments. Will try to post the code as well.

3. Next Palindrome
Find the next palindrome. Input is an integer and output should be the palindrome integer which is higher than the input.

Example:
Input: 12345
Output:12421
Input:111
Output: 121

4. Maximize the Time to see TV
There is a TV avid person. HE wants to spend his max time on TV. There are N channels with different program of different length and diff times. WAP so that the person cam spend his max time watching TV.
Precondition: If that person watches a program, he watches it completely.

Ex:
Channel1: prog1 – 8:00- 8:30
prog2: 9:00 – 10:00
prog3: 10:15 – 12:00

channel2: prg1 – 8:15 – 10:00
prg2: 10:30 – 12:00

So in this case max time will be if he watches:

ch2/prg1 + ch1/prg3

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

25 Responses to Programming Problems 1

  1. Amar says:

    1. Find the least power of 10 less than a. convert it into a sequence of 4’s(4444….).
    Now this sequence will be less than a. Increment the sequence till you start getting numbers between a and b. Count the number of sequences between a and b. That’s your answer.

    To increment the sequence of only 4’s and 7’s.
    Start with the current digit(last digit) of current number, if the current is 4 change it to 7 and if it is 7 set the current digit to 4 and go to next digit to the left. If all the digits are 7 add a 4.

  2. Amar says:

    3. Even number of digits. Traverse the digit. Make the lower half all zeros. When you reach the upper half copy the digits on the lower half in reverse manner.
    For Odd number of digit you need to omit the middle digit while traversing.

    Sounds easy enough …. 🙂

  3. Avi Dullu says:

    yes .. these questions were starters 🙂

  4. Amar says:

    4. Lets say each channel is represented by an array of structure of program timings.
    i.e.
    struct program{
    double start;
    double end;
    };

    program channel1[10];
    program channel2[11];
    and so on….
    from each array find out the program starting first then try finding the next program and so on. Calculate and maintain a local sum and a global max.
    Finally the global max will give the value.

    I will post a program in the next comment….. 🙂

  5. spandan says:

    can anybody tell me the complexity of amar’s algo to ques1.

  6. Rani says:

    sir, can you please post the solution or a hint for Q2 (Ideal String) .. thank you

    • Avi Dullu says:

      just check if the given number is of the for n*(n+1)/2, if it is, then just output the string ABBCCCDDDD… for n alphabets.

      • Rani says:

        1) if N == n(n+1)/2 the answer will be ABCDBCCDDD and so on ..

        2) even this is nt the complete solution, I guess .. take an example of n=7, I can easily form a string ABBCCCA .. evethough (n(n+1)/2)!=7 for any n.

        By getting n, such that n(n+1)/2 < N (given num), it only guarantees me the number of different alphabets that can be used. We need to arrange these alphabets in certain order to get the output. I am unable to produce a solution, except brute force, for ordering these alphabets. Can you please suggest ..
        thank you

  7. Avi Dullu says:

    @Rani
    If you would notice, the problem asks you for the lexicographically smallest string.
    And for you point 2, just go through the qns again. The string which you have given has A, 2 times which is forbidden by the problem.

    • Rani says:

      The answer for N=10 should be ABCDBCCDDD … if the answer for this is ABBCCCDDDD then it does not satisy the constraints of the question because C occurs 3 times and its first occurence is at #4(Contradiction) whereas it should be at #3. Similarly for D which occurs 4 times but its 1st occurence is at #7(Wrong).

      For my 2nd doubt, it was a typo 😦 .. for N = 7, it should have been ABBCCCC .. here A occurs once and so its first(&only) occurence is at #1 .. similarly B occurs twice and so its 1st occurence is at #2 .. and C occurs four times and hence its first occurence is at #4 ..

      kindly clarify ..

      thank you …

      • Avi Dullu says:

        sorry my bad, I posted the wrong solution.
        The part in which I formed the string was wrong. If N (input) = n*(n+1)/2, then form the string in the following way
        ABCD..n alphabets and then start inserting remaining alphabets like 1 B, 2 Cs, 3 Ds, 4 Es etc.
        so for N = 15, ABCDEBCCDDDEEEE

  8. Rani says:

    As I’ve already mentioned in my previous post that the part when N = n(n+1)/2 is clear, but what about when N!=n(n+1)/2 .. eg the case that I posted above (N=7) .. just wanted to know if there is a better solution other than brute force ?

    • Avi Dullu says:

      @Rani
      I completely forgot about your doubt (and my wrong solution) since I was very very busy. I did look into it now and I guess am very close to an optimal solution. Here it is
      The idea is to find out first whether the given integer can result in an ideal string. To do this, we add 1 character into the string in each step and find out all possible lengths of ideal strings which it can result in. eg. 2 alphabets can only give ideal string of length 3 whereas 3 alphabets can give ideal strings of lengths 6 and 7. Now if you add another alphabet to ideal string of 3 alphabets you have these positions where you can insert it 4,5,6,7 and 8. (since there are 5 positions where next alphabet can be inserted) Now you can see that 4 alphabets can result in ideal strings of length (6+4), (6+5), (6+6), (6+7), (7+5), (7+6), (7+7) and (7+8). So 4 alphabets can form ideal strings of lengths 10,11,12,13,14 and 15. Similarly you can find out all the lengths which have valid ideal strings and with this procedure you can also remember the configuration which resulted in that ideal string.
      Hope I was clear enough, will update the solution above and try (seriously) to code it and provide it to you.
      PS: This problem seemed to be quiet a nut to crack :). Thanx for pointing out the flaw.

  9. Redpage says:

    Just felt like coding this one 😛
    //Tail represents the last unique character position, elements the total number of elements so far, n is the number which we are trying for ideal string
    Ideal String code –

    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    
    int existsIdealString(int tail, int elements, int n, char *position) {
      if (elements > n)
        return 0;
      if (elements == n)
        return 1;
      for (int i = tail + 1; i <= elements; ++i) {
        if (existsIdealString(i, elements + i + 1, n, position)) {
          position[i] = '1';
          return 1;
        }
      }
      return 0;
    }
    
    void makeString(char *position, int n) {
      char *buffer = (char *)malloc(sizeof(char)*n);
      int start = 0, end = 0, index = 0;
      for (int i = 0;i < n; ++i) {
        if (position[i]) {
          position[i] = 'a' + index;
          for(int j = 0; j < i; ++j) {
            buffer[end++] = 'a' + index;
          }
          ++index;
        }
        else {
          position[i] = buffer[++start];
        }
      }
      free(buffer);
      printf("%s\n", position);
    }
    
    int main(int argc, char *argv[]) {
      int number;
      scanf("%d", &number);
      char *position = (char *)malloc(sizeof(char) * (number + 1));
      memset(position, 0, number + 1);
      if(existsIdealString(-1, 0, number, position)) {
        makeString(position, number);
      } else {
        printf("That number doesn't make for an ideal string\n");
      }
      free(position);
      return 0;
    }
    
    
    • Avi Dullu says:

      I don’t think this works 🙂

      • RedPage says:

        Really? I seem to be getting the correct output until 31. Could you tell me for which number is it not seemingly working?

      • RedPage says:

        Really? I seem to be getting the correct output until 31. Could you tell me for which number is it not seemingly working?
        I have not put a restriction on the base case. If that is what you were saying. Beyond ~400 as input it takes characters that go beyond z.

      • RedPage says:

        Umm with this code it works fine till 495. After that it gives a constant length wrong answer(460 characters apparently). So I thought there was a problem with the new character being introduced after ~. If I change the characters to capitals after the small letters have been exhausted(index variable in the code goes beyond 26), the code gives me a correct output.

      • Avi Dullu says:

        I tested ur code on some input cases. Here are the results.

        10
        abcdccddd

        12
        abcccdddddd

        If these do not match your results, please re-post the code, with the formatting style I mentioned.

  10. Redpage says:

    And the formatting gets screwed.

    • Avi Dullu says:

      u need to use a special tag open square backetsourcecode lang=”C” … code … open square bracket/sourcecodeclose square bracket. Have updated your code.

  11. RedPage says:
    #include <stdio.h>
    #include<stdlib.h>
    int existsIdealString(int tail, int elements, int n, char *position)
    {
            if (elements > n)
                    return 0;
            if (elements == n)
                    return 1;
            int i;
            for (i = tail +1; i<=elements; i++)
            {
                    if (existsIdealString(i, elements+i+1,n, position))
                    {
                            position[i] = '1';
                            return 1;
                    }
            }
            return 0;
    }
    void makeString(char *position, int n)
    {
            char *buffer = (char *)malloc(sizeof(char)*n);
            int i,start = 0, end = 0,j,index = 0;
            for (i=0;i<n;i++)
            {
                    if (position[i])
                    {
                            if(index<26)
                                    position[i] = 'a'+index;
                            else
                                    position[i] = 'A' + index -26;
                            for(j=0; j<i;j++)
                            {
                                    if (index <26)
                                    buffer[end++] = 'a' + index;
                                    else
                                    buffer[end++] = 'A' + index -26;
                            }
    
                            index++;
                    }
                    else
                            position[i] = buffer[start++];
            }
            free(buffer);
    
            printf("%s\n",position);
            return;
    }
    int main(int argc, char *argv[])
    {
            int number;
            scanf ("%d",&number);
            char *position =(char *) malloc(sizeof(char)*(number+1));
    
            memset(position,0,number+1);
            if(existsIdealString(-1,0,number,position))
                    makeString(position,number);
    
            else printf("That number doesn't make for an ideal string\n");
            return 0;
    }
    

    From what I see, in the previous code, the incrementing of i++ and j++ has been changed to ++i, ++j

  12. Oppilas says:

    Unlucky Numbers

    #include <iostream>
    #include <cstdlib>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>

    using namespace std;
    void solve(int a,int b,int n, int &ans){
    if(a<=n && n<=b) {ans++; cout<<n<<" ";

    solve(a,b,(n*10)+4,ans);
    solve(a,b,(n*10+7),ans);
    }
    return ;
    }
    int main(){
    int a,b,ans,cases;
    cout<<"Enter test cases =";
    cin>>cases;
    while(cases–){
    cout<<"Enter a, b :";
    cin>>a>>b;
    ans=0;
    int four=0,seven=0;
    { int temp=a; while(temp){
    temp/=10;
    four=four*10 +4;
    seven=seven*10+7;
    }
    }
    solve(a,b,four,ans);
    solve(a,b,seven,ans);
    cout<<"\nFinal count= "<<ans<<"\n";
    }
    return 0;

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: