# Programming Problems 1

October 1, 2009 25 Comments

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

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.

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 …. 🙂

yes .. these questions were starters 🙂

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….. 🙂

This is a type of Interval Scheduling Problem. Just scrutinize the approach you have suggested.

I will

highlyappreciate a program by you. 🙂can anybody tell me the complexity of amar’s algo to ques1.

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

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.

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

@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.

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 …

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

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 ?

@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

lengthsof 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.

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 –

I don’t think this works 🙂

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

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.

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.

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.

And the formatting gets screwed.

u need to use a special tag

open square backetsourcecode lang=”C” … code …open square bracket/sourcecodeclose square bracket. Have updated your code.From what I see, in the previous code, the incrementing of i++ and j++ has been changed to ++i, ++j

This seems to work. Thanx for posting the code 🙂

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;

}