• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

programming questioin

 
amit taneja
Ranch Hand
Posts: 813
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
=============================================================

Problem Statement
����
A sequence of integers
(a1, a2, a3, ..., an)
is called arithmetic if a2 - a1 = a3 - a2 = a4 - a3 = ... In order to make the given sequence arithmetic, you are allowed to replace each element with a different integer value (no fractions allowed). Unfortunately, each such replacement has an associated cost of 1. Return the minimum cost required to make the given sequence arithmetic. If the given sequence is already arithmetic, return 0.
Definition
����
Class:
ArithmeticReplace
Method:
howMany
Parameters:
int[]
Returns:
int
Method signature:
int howMany(int[] seq)
(be sure your method is public)
����

Notes
-
An element can be replaced by a value less than -10000 or greater than 10000.
Constraints
-
seq will contain between 3 and 50 elements inclusive.
-
Each element of seq will be between -10000 and 10000 inclusive.
Examples
0)

����
{1,4,7,11}
Returns: 1
Replacing the 11 with a 10 we get an arithmetic sequence.
1)

����
{-10,-5,0,5,10,15}
Returns: 0
This sequence is already arithmetic.
2)

����
{157, 119, 15, -5, -25}
Returns: 2
Replacing the first two elements with 55 and 35 we get an arithmetic sequence.
3)

����
{1,2,4,7,11,16,22,29,37,46,56,67,79,92,106}
Returns: 13

4)

����
{1,100,10,40,2,200,-71,250,99,103,325}
Returns: 7
===============================================
.............

we add solutions...
can anybody make it further correct...
coz we are able to find out the correct result by adding further code to that but that doesn't make the series in AP

see the question is asking that find out how many numbers we should add to make the series to be in AP .. even if we find the anwer we are not able to make the series in AP...


here is my code

-------------------------


import java.util.Arrays;

public class ArithmeticReplace {
int counter = 0;

public int howMany(int[] seq) {

Arrays.sort(seq);
System.out.println("length " + seq.length);
for (int i = 0; i < seq.length; i++)
System.out.print(seq[i] + " ");
int dif = 0;
System.out.println("diff " + dif);
int[] a = new int[seq.length - 1];
for (int i = 0; i < seq.length - 1; i++) {
// System.out.println("each diff " + (seq[i + 1] - seq[i]));
a[i] = seq[i + 1] - seq[i];
System.out.print(" " + a[i]);
}
System.out.println();
System.out.println("a length " + a.length);
Arrays.sort(a);
for (int i = 0; i < a.length; i++)
System.out.print(" " + a[i]);

int n = 1, k = 1, l = 0;
for (int i = 0; i < a.length - 1; i++) {
if (a[i + 1] == a[i]) {
n++;
l = a[i];
} else {
if (n > k) {
k = n;
l = a[i];
}

n = 1;
}

}
System.out.println();
System.out.println("l " + l);
System.out.println("k " + k);
dif = l;
// seq.length-k*2;
for (int i = 0; i < seq.length - 1; i++) {
if (seq[i + 1] - seq[i] != dif) {
counter++;
}
}
// if (counter > 0)
// counter++;
return counter;
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

ArithmeticReplace ar = new ArithmeticReplace();
int k = ar.howMany(new int[] {1,100,10,40,2,200,-71,250,99,103,325});
System.out.println("k>>>> " + k);
}

}


-----------------------


thanks

[ April 09, 2006: Message edited by: amit taneja ]
[ April 10, 2006: Message edited by: amit taneja ]
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
but that doesn't make the series in AP

I don't understand the question - what is AP?
 
Ryan McGuire
Ranch Hand
Posts: 1048
4
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by amit taneja:
Problem Statement
-------------------------

package google;



The problem statement isn't another copyrighted one that shouldn't be reproduced, is it?
 
Ryan McGuire
Ranch Hand
Posts: 1048
4
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Stefan Wagner:

I don't understand the question - what is AP?


AP is Arithmetic Progression.
 
amit taneja
Ranch Hand
Posts: 813
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yes AP is Airthmatic progression

kindly help to solve this program question.. its challenging
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well - I don't understand that sentence:
see the question is asking that find out how many numbers we should add to make the series to be in AP .. even if we find the anwer we are not able to make the series in AP...

How can you find an anwer, which is not making the series in AP?
 
amit taneja
Ranch Hand
Posts: 813
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the orginal problem is within the ================== lines in first post of this thread...

please read carefully and then try to understand what the question is saying ...
 
Steve Fahlbusch
Bartender
Posts: 602
7
Mac OS X Python
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm with Stefan - and while I understand the assignment (but there are a few problems with the defn (look at the notes)

"How can you find an anwer, which is not making the series in AP?"

By defn, if you find an answer, then have you have to have a series in AP.
 
amit taneja
Ranch Hand
Posts: 813
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i think the question is wrong....
or some stuff is missing..
but this is the original question ....nothing i missed up in copy paste
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So, rather than answering Ryan's question, you simply tried to delete the evidence? No good - we remember what it said earlier. You've asked several past questions from Google CodeJam problem sets which violated their copyright. Why not be honest about where this stuff comes from? If it's from one of their old problem sets, post a link to where it can be viewed. If it's from a new (current) problem set, then please don't post at all.

[amit]: see the question is asking that find out how many numbers we should add to make the series to be in AP

No, it asks how many numbers you should replace. You can make any sequence arithmetic if you replace enough numbers; the trick is to find the minimum required.
 
Ryan McGuire
Ranch Hand
Posts: 1048
4
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I had to write the program just so I could see how they came up with 7 for the last example. Oh, I see now... the difference between consecutive terms is 25, starting at 75. So 100, 200, 250 and 325 stay, while the rest get replaced.

(Besides I needed an excuse to used my Mixed class for fractional numbers again. )

I have one algorithm. Has anyone else figure this out yet?
 
Steve Fahlbusch
Bartender
Posts: 602
7
Mac OS X Python
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ryan,

When I looked at this earlier, I had a trivial but very inelegant solution (looking at all pairs of two elements, if the delta is valid - expand a new arrar and save the array that had the fewest replacements).

-steve
 
Ali Hussain
Ranch Hand
Posts: 211
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Ryan McGuire:


The problem statement isn't another copyrighted one that shouldn't be reproduced, is it?

From the format of the problem statement, it seems to be taken from topcoder.com.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ryan and Steve: yeah, I had made a quick solution similar to what Steve describes. There are various optimizations that can be made along the way, but it's still fundamentally an O(n^3) algorithm as far as I can tell. I don't think it's quite as inelegant or trivial as stave makes it sound, but it does feel like there ought to be some more clever solution possible. There's a certain temptation to apply an FFT or something to try to find the strongest underlying patterns more quickly. Which is probably overkill, but oh well. More to the point, I don't think it would actually work. But there's a lingering feeling that something similar might. Unfortunately, I don't see a specific avenue to pursue. So for now, I'll content myself with O(n^3), I guess.
 
Ryan McGuire
Ranch Hand
Posts: 1048
4
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rather than figuring out all the values in the modified sequence, I just figure out the slope and y-intercept implied by each pair of points. If the slope is an integer (i.e. differenceBetweenTwoValues % distanceBetweenThem == 0) then I save that slope/intercept pair. The slope/intercept pair that's used between the most pairs is the one that would be used for the "repaired" sequence (if I bother to figure it out).

For example...
Original sequence: {20,24,29,32}
slope=4, intercept=20 is used between 3 pairs: 20-24, 24-32, and 20-32.
slope=non-integer between 20-29, so ignore it.
slope=5, intercept=19 is used between 1 pair : 24-29
slope=3, intercept=23 is used between 1 pair : 29-32

Since (4, 20) is the most popular pair, it would be used for the final sequence.

BUT... I don't even need to figure out what the new sequence is. Rather than comparing old values and new values, I can determine how many values would have to change with the following equation:

NumberOfReplacements = sequenceLength - (sqrt(8*Pairs + 1) + 1)/2

where "Pairs" is the number of pairs in the original sequence that used the most popular slope/intercept pair (3 in the example above).

Let's see... 8*3 = 24. 24+1 = 25. sqrt(25) = 5. 5+1=6. 6/2=3. 4-3=1. So the return value is 1. (I love the quadratic equation.)

Since I don't calculate the whole new sequence implied by each pair, my alg is only O(n^2).
[ April 20, 2006: Message edited by: Ryan McGuire ]
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ah, nicely done. I had started down a similar route, but I was considering only slopes, not intercepts. When I saw this was insufficient, I jumped to considering all points, when I should have considered slope plus intercept. Seems obvious in retrospect.

The one advantage I can see for my solution is that it doesn't require any substantial memory or other storage, as I don't need to keep cumulative counts for a bunch of different slope/intercept pairs. In most cases this is a minor issue, as memory is cheap. But since the memory usage in your solution is O(n^2) (right?), in some situations it may be necessary to switch to a less memory-intensive algorithm. Though of course you could also use a database of some sort instead, ultimately relying on some file-based storage I assume.

Anyway, good job.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic